I too absolutely loved Super Mario Sunshine - it was just fun! Plus the music was amazing.
My most memorable game, was a Sega Megadrive game named Soleil. It was the story, the visuals, the gameplay, the challenges and the music that were amazing.
You played a boy who just turned thirteen, and had to defend the town from "monsters". Suddenly one day, when playing the playground, a witch puts a spell on you, and you can no longer understand humans, but can talk to animals. You start to see the world from the animals' perspective, and by saving the animals, they offer to help you in return. It puts a great spin on the idea of what a monster is, as at one point you get transformed into a "monster" and a "hero" tries to kill you... he's rather strong too. On return to your "monster" family, you see that they just want to be left alone. It covers lots of locations, from beaches, towns, icecaps, deserts and underwater too.
The game also went by the name "Crusader of Centy" .. or something similar.
I doubt you'd be able to find a cartridge these days, though I know if you're adamant on playing it, you can.
I'd love to remake this game in 3D...