As for science fiction, Amen wanted to start an Alpha Centauri NES. Now that we begun talking about it, how about a Master of Orion NES? I think the setting is quite good, all that is needed is a nice little rule set. Or maybe a NES set in another science fiction universe, where everybody could design his own race, with its own strenghts and weaknesses? Once more, the Dune NES suggestion remains open. In the past there were a few attempts to make a Starcraft NES (didn't work out because of lack of a map). It's worth another try.
How about a Warcraft III NES? Or an Age of Mythology NES? There is more to fantasy then LotR... Maybe a "random map" fantasy, with everybody being a mage with slaves, minions, summons and mercenaries, while the NPC kingdoms struggle against each other and ask for your help occasionaly?
I would really like to see a "random map" NES, simply because that in these you could name everything and create a new culture from an empty place.