Kirby's Dream Land 3 and Kirby Super Star are excellent two player games (plus it'll give you some practice for 2 player Adventure Mode in SSBB).

Other good 2 player games are Double Dragons, Wario's Woods, Contra, Secret of Mana, Aero Fighters, and Battle City.

The Lawnmower Man is a really weird (but fun) game.

That's all I can think of right now.

No wait, there's also Ice Climber (I can't believe I almost forgot that one), Balloon Fight, Devil World, and Clu Clu Land.