Your fallacy is you are equating "most colors on screen" with "best looking".
As has already been explained, putting 25 colors on the screen at once is not difficult and is something the NES is fully capable of doing without any tricks. Most games just don't do it, however, because it wouldn't look very good since each 16x16 block is restricted to 4 colors.
If you are interested in the technical limitations of the NES, you need to look no further than the palette/PPU viewer in an emu like FCEUX:
This is from Final Fantasy. The circled color is the background color. The X'd out colors are not actually visible (they're transparent -- hard to explain). But everything else can be unique.
Everything else is 3*8 = 24, plus the background color is 25.
Note, however, the duplicates. There's a lot of black in the bottom row because sprites want to have a black outline, and so every sprite palette also needs to have black in it. There's also lots of greens because this is from the overworld and pretty much every tile on the overworld has some part of it that's grassy, so every palette also needs a green.
Now, you could VERY EASILY change all those duplicate colors to all be unique. And that would not be technically difficult at all -- a totally novice romhacker could do it for their very first hack. But it would probably look like absolute garbage. The map would look extremely blocky as there'd be rigid/hard color breaks on 16x16 boundaries when the palette changes.