Contra + Super C are definitely up there, as is Blades of Steel. I thought the original Ice Hockey wasn't too bad, either, but you couldn't throw off the gloves and fight The Turtles games were r0><0r, too.

I don't know about the Mario games for 2-player...they were great, but IMO 2-player works best when you have both people on the screen at once.