I went on a big SMS kick a few years ago, mainly some of the PAL titles since, even though seeing SMS games in my area was very rare, I wanted to try out some stuff that was released in Europe where the console was quite successful.
If you are going to look for PAL games and cannot find any locally and have to resort to Ebay, I recommend doing worldwide searches and buying from European or Australian sellers.
Some of these have already been mentioned, but here's my two cents:
Asterix Series:
- Asterix
- Asterix and the Great Rescue
- Asterix and the Secret Mission
*The Asterix titles are all solid platformers.
The Disney Games:
- Castle of Illusion starring Mickey Mouse
- Land of Illusion starring Mickey Mouse
- Donald Duck's Lucky Dime Caper
- Deep Duck Trouble starring Donald Duck
They are not as good as the NES Capcom Disney games, but they are solid, straightforward platformers if that is something you enjoy.
- Master of Darkness
A great Castlevania style game. Not as fun as the original Castlevania, but a solid title nonetheless.
- Ninja Gaiden
It's cool because it is not like the NES or PCE versions. The level layouts and bosses are different. I'm not the biggest fan of the SMS controller, but the controls in this game work surprisingly well. Having the pause button on the console will become a big bother in this game when you want to quickly pause the game to access the situation you are in.
Sonic Games
- Sonic 1
- Sonic 2
- Sonic Chaos
I was never really impressed by the "speed" aspect of the Sonic games on the Genesis. It just didn't appeal to me. I actually prefer these versions because there's more emphasis on platforming and correctly timing your jumps. Sonic Chaos is a little too easy though if you don't pay attention to getting. The hangliding parts of Sonic 2 are pretty cool.
And of course there's always any of the Wonder Boy series games.