Plok is an old hidden gem of an SNES platformer. Your limbs are your weapons and it's got a decent plot and some fun vehicle sections.

Only mentioning it because probably no one else will.

Just off the top of my head (I'll probably add more later). I'm listing games where two players aren't playing simultaneously as "Single Player" for some reason. Especially in the "Two-Player" category, these represent games I've had tons of fun with on the original systems.

NES
(Single Player)

• Adventures of Lolo (any/all)

• Bionic Commando

• Castlevania

• Castlevania II: Simon's Quest

• Castlevania 3

• Legend of Zelda

• RC Pro-Am

• Super Mario Bros. 3

• Wizards and Warriors

(Two Player)

• Battle City (on 31-in-one disc)

• Contra

• Super-C

• Double Dragon II

• Dr. Mario

• Mario Bros. (the original, also called "Mr. Mary" on a 31-in-one disc)

• Jackal

SNES
(Single Player)

• Act Raiser

• Castlevania IV

• F-Zero

• Legend of Zelda: A Link to the Past

• Super Mario World

• Star Fox

(Multi Player)

• Mario Kart

• Super Bomber Man

• Street Fighter 2

Damn, beat me to it. You can also emulate Melee(Gamecube) as well with Dolphin.
One liner for Smash Bros.? A pretty unique fighting game which is great for both skilled and non-skilled players.

Also, I should point out that if you're looking for 2 player action, you could obviously emulate some Neo-Geo classics. Try putting a set amount of credits on Metal Slug 3 and see how far you can go. (And you can cheat your credits to play through the whole game).

I remember playing the N64 version a lot. The stages were very fun, even though as you say, the multiplayer was crippled. I find it a bit boring there's no music and an annoying "dancing" sound+pause when only one car is left on the screen. It was still a very fun game, going in a circuit through a baguette trying to get to the other table, hitting a cellphone and it rings. Entering a small sand castle in the beach. Lots of goodies in there.

Nobody mentioned Battletoads(Genesis)?

Chrono Trigger, terranigma, Yoshi's Island, Ogre Battle

Metal Slug 4 (Mame)

Goof troop on the SNES is aimed at young children, so it may not be your thing. But I always found it surprisingly fun especially because of its multiplayer mode.

Was that the origional Gauntlet which was a fun dungeon crawl, or the new one where you eventually fight a boss?

Radical Psycho Machine Racing was pretty fun. Off-Road was great.

For multiplayer retro gaming I have to second the metal slug recommendations. Probably one of the fondest highschool date memories I have was taking a totally non-nerdy girl home and playing the neo-geo arcade emulator (it's part of mame now I think) with a couple of the metal slugs games through with her. They're fantastic. Think contra, but with decent graphics, and a ton more polished, and all kinds of random things like "oh you're stuck tap left right left right" or oh, quick kill those dudes before they become mummies. Definitely play it on mame, because you can keep putting quarters in and get through it, you will die a thousand times and keep coming back for more.

For SNES I would say super smash T.V. was my all time favorite, for Genesis it would be streets of rage, and for NES, I know it sounds lame, but monopoly. You can do everything in the regular rules (plus setup extras like free parking and what not), and it's the most polished and fun monopoly game I've ever played, you can hash a decent game out in an hour, or an hour and a half, it even talks, like when you get out of jail it's all "Don't be coming back now" and stuff. The snes/psx/pc and other (even modern ports) I've seen so far have NOT come close to the NES monopoly. Also, I think it's more than 4 players, but I know it's at least that.

@bamccaig there are other ways to get dates?