I would strongly recommend Top Hunter (Neo Geo) to any VC user looking for a strong two-player game. It's a side-scrolling platformer-beat'em up hybrid set across a variety of hugely atmospheric levels. Jump up to reach platforms, jump between separate foreground and background planes, grab on to ledges by stretching your arms, grab and throw enemies or beat the crap out of them. Graphics and sound are very good, and the refined gameplay just plain rocks.
If, after playing Top Hunter to death, you're looking for even more two-player platforming action, I'd also recommend you consider Blue's Journey. It's not just a "kiddie game", as some has stated, but actually a pretty good platformer in it's own right, and two players get to play co-op without it turning competitive.
These are two games that deserve to sell better, in my opinion.