You have a GC, so get OoT/Master Quest in the Wind Waker special edition. If you didn't know the GC version not only comes with Master Quest (a version of OoT with remastered dungeons), but also plays in 60hz (the N64 and VC versions only play in 50hz here in PAL regions).
Super Mario 64 is amazing, but I myself prefer the DS version (puts up flame shield). However keep in mind the VC version will be considerably cheaper though.
Super Mario Kart is a game that IMO hasn't aged too well (again puts up flame shield), that's not to say it isn't good. I would recommend getting Mario Kart SC for the GBA as it has all the tracks from SMK.
Donkey Kong Country is another kick arse game, but I would recommend DKC2 instead as I think it is a better game.
That leaves Super Metroid and Super Mario RPG, both are amazing and I would whole heartedly recommend either of them. Though I would like to say that if you want an RPG with Mario characters, I prefer Paper Mario to SMRPG (for the third and final time puts up flame shield).
Hope that helps!
