One game that no one will ever mention, that impressed me, was Greg Norman Golf Power. The game redraws a 3D picture of the golf course after every shot, which is way beyond what every other NES game was doing, and closer to what StarFox and Doom are doing (even if very slowly, and not animated).
Not a great game, though.
-------------------------
nesdoug.com -- blog/tutorial on programming for the NES