City Connection, Bugs Bunny's Crazy Castle. While neither are co-op my mom and took turns playing crazy castle on the nes when I was a kid and we beat it. Core memory right there.
I think Tetris or Doctor Mario had 2 player modes but I'm not sure.
Does Sonic Spinball on the Genesis have multiplayer?