Here are a few recommendations that I'm pretty sure haven't been mentioned already.
Lemmings - This port of Lemmings is substantially different from all others, and contains a huge number of exclusive levels not found in any other version of the game. Even if you have it for another system, this port is worth getting if you want more puzzles.
Lemmings 2: The Tribes - I think that this is the best version of Lemmings 2. It has fantastic music that's different to the other versions (though it shares some tracks with the Archimedes release, which was ported by the same outfit), too.
Puggsy - Very clever physics-based platform-puzzler that was decades ahead of its time. There is an Amiga version (naturally, since the game is a result of Psygnosis buying the rights to the character from the "Puggs in Space" demo for the Amiga), but it's not quite as polished-looking as the Mega Drive one - not to mention, the game really needs multiple controller buttons to be enjoyable.
Mickey Mania - The Timeless Adventures of Mickey Mouse - A must-play platformer, this one being based on a number of Mickey Mouse's classic short cartoons. It's full of brilliant moments and clever touches, and is the only Disney-licensed product in which Mickey Mouse can be seen to die! (True story!) I'd call the Mega Drive version the definitive one, especially since (in my opinion) it has better music than the Mega CD/PSX version, and because Travellers' Tales mysteriously crippled the SNES version by entirely removing large sections of levels, jumbling up the music and playing the wrong pieces in the wrong places, and adding fake loading screens into it for no apparent reason.
Sparkster - Rocket Knight Adventures 2 - Another platform game. No relation to the also-excellent SNES game in the series (which was simply named "Sparkster", minus the subtitle), and the direct sequel to Rocket Knight Adventures, this one's worth a look. You've got better control over your rocket-pack in this game, and it's got that difficult-to-quantify fun-factor about it (some of which doubtless comes from how well-done the rocket-pack mechanics are - it really makes you wish you could have one for real!
).
Psycho Pinball - A pinball game featuring great presentation and physics, and four different tables. It's easily on-par with the likes of Pinball Dreams on the Amiga. There was a "Double Hits" budget re-release of this that came with Micro Machines on the same cartridge (on which you can only switch between the two games by pressing the reset button, as there is no menu) - if you're planning to pick up Micro Machines as well, it's worth grabbing this release.
You also probably can't go far wrong with looking up a few of the
Mega Games compilations that Sega released, which each contain multiple popular games for the system. Whilst they were also available at retail, they were often bundled in with hardware during the system's later years, so should be plentiful.
