Eternal Champions - Sega CD (far better than the cartridge version) - A 1-on-1 fighter that put Mortal Kombat to shame. Awesome story. Awesome cinematics that told every character's story and showed their death. TONS of characters (mostly hidden). Tons of moves. Tons of way to horribly finish off your opponent.
Shadow Squadron - Sega Genesis 32X - A simple polygon space shooter. It's the best space shooter I've ever played. (I haven't played a lot, but the few I have really disappointed me.) It was simple, yet complex. It was spacious. It felt like outer space instead of some big 3D arena roped off for me to fight in. i.e. I don't think I ever hit an invisible wall. The 3D map was simple yet superb. I don't know why all space combat games (and even aerial combat games,) don't use it. I loved being able to blow up the big ships piece by piece. There was 1 ship one player would use. If 2 players played, another ship was used. One flew, the other manned the gun. The ships were so different, the only way I could beat the game was to fly the 2 player ship all by myself. (I won't go into anymore detail though.)
Black - Xbox/PS2 - Not very old, but man, that was one awesome FPS! Superb graphics that got even better when enhanced slightly by the 360; superb sounds for the guns & explosions; excellent explosions & particle effects; Unlimited ammo was unlockable, (very awesome with missions that had a rocket launcher); and you got to partially destroy a building once in a while.
Archon - A kind of battle chess game, but not actually chess. Who wins decides on actual combat between magical beings. I haven't played that since it was on the ancient Atari 800XL.
Rallyway - another one form the Atari 800XL. It's a top down racing game that was a favorite of my brother & me back in the day. 2 player, and it actually had a map making feature. Every curve, bush, building, and puddle that was in the normal game you could place however you liked to make your own track. You didn't even have to have a complete track. Unfortunately, there was no ability to save your own tracks, and making them took forever.
Speaking of Atari games, I wonder what a remake of Combat would be like. I'm sure it'd be nearly unrecognizable with all the updates they'd shove into it.
...and I'll second Vigilante 8 & 2nd Offense, but only if they put the original V8 handling in 2nd O. Control was perfect in the 1st game, but horrid in the sequel! On top of bad basic control, those ski's & water attachments were so hard to control & didn't even bother with them.