I think both of the last edits look good, and the lower-saturation colours of the bottom one are lovely, but I feel there were some contrast issues, and you may have gone a bit
too desaturated. Here's an edit that tries to blend the two of them:
(As a bonus, in my editing I somehow managed to get it down from 48+ colours to 31.)
I decreased the contrast on flat surfaces (walls, ground, etc), so that they look more solid. This had the bonus effect of making the characters stand out better. The most important areas where this makes a difference are the stairs outside, the grey dungeon tiles, and the grass, though I think it helps everywhere at least a little.
I changed the black from pure black to dark red because that feels a bit less dull, but it'll work fine if you change it back to pure black.
The NES palette can't handle this sort of thing, as it lacks this much variety in midtones. The same is true for your other colour mock-ups though. Here's what a NES version of my edit might look like (23 colours!):
(Note that some tiles don't quite meet NES specs.)
