For the Genesis I'd nominate Vectorman. It's on the VC, on the old Genesis Collection for PS2 and Xbox, and on Sonic's Ultimate Genesis Collection for PS3 and 360, so it's really easy to get a hold of.
I actually never played this game back in the day, though I thought it looked cool. I got the chance when the Genesis collection released on the PS2, and while at first I thought it was underwhelming, the more I played, the more I liked it.
It's very score-oriented and the stages have a time limit, which might put some people off, but the action is fast, and there's some depth to it. The thing you have to understand if you want to have a hope to complete the game is that the multiplier doesn't just multiply your score, it also multiplies the lives you pick up. So there's some strategy to it: someone who's memorized where the multipliers and the lives are can rack up tons of lives, which will make the game a lot less frustrating.
The platforming levels are varied, and non-platforming stages offer even more varied gameplay.
I loved it and only played it 2 years ago, so I think it's a title that holds up.