Zelda: Windwaker - It's a zelda game, no more explanation needed.
Metroid Prime 1 and 2 - Both games are incredibly fun, it retains all the great feeling of the original metroid, but implements it perfectly into a first person view. It definately doesn't feel like an FPS, a very unique, and fun experiance.
F-Zero GX - An absolute blast, one of the best racing games ever released. The frenetic action of 30 cars screaming across insane tracks at 2000+ mph can't be simulated in any other game. Also, if you like hard games, you'll love this. The story missions on very hard will kick your ass like no tomorrow, and don't plan on beating a staff ghost anytime soon.
Resident Evil 4 - One of the best, if not the best game released on this generation of consoles. The graphics are unbelievable, the gameplay is perfect, and the fun factor is through the roof. If you only get one game for the GCN, it has to be this game, no excuses.