I'd be here all night if I'd make a list of games you should download. For WiiWare, do get Strong Bad's game, maybe Dr. Mario RX if you like Dr. Mario, and save the rest for May-guh Man Nine!! :D
For VC games, I'd tell you to get Phantasy Star II, but if you have a PS2 or PSP, you could just get SEGA Genesis Collection and call it even. Plus, you'd get a chance to play Phantasy Star IV to boot... ;)! But if you need to download a Genesis title that's not on the batch, go with Shining Force. It's SEGA's answer to Fire Emblem, and it's a lot better. You actually get to fight monsters (well, save for Fire Emblem 8: The Sacred Stones, of course) instead of generic humans that seem to share a strange resemblance.
For a platformer, you should download DoReMi Fantasy: Milon No Doki Doki Daibouken. I dunno what it means either, but it's a wonderful Super Mario World clone that is the sequel to Milon's Secret Castle on the NES. Now, it certainly is different than what you're used to, but that shouldn't stop you from enjoying it.
Mega Man
A good game, aye, but you couldn't he just get Mega Man Anniversary Collection? River City Ransom is a good suggestion though. I hope you have a friend to play with, LuiKang!