The Gamecube was my first Nintendo-console so it's just relative 'new' games in my list. Despite the fact that I have played Zelda TWW and OoT (and am in the process of playing The Minish Cap) there's no Zelda in my list hahaha!
1. Metroid Prime (GC)
The reason why I bought my GC. I had high expectations of this game and it surpased them by lightyears. Absolutely perfect.
2. Mario & Luigi: Superstar Saga (GBA)
The best and most funny action RPG on a handheld I ever played. I started playing it and just couldn't stop. Actually: this 'sub-franchise' may have surpassed the games it was based on.
3. Paper Mario: The Thousand Year Door (GC)
See nr. 2 but then for a console.
4. Advance Wars (GBA)
The game that revived my love for strategy. Big, brilliant, and so much fun. Dual Strike is probably better and even more polished but this one started it all.
5. Mario Kart DS (DS)
I played Double Dash and Super Circuit but this one is the ultimate kart-racer and the best handheld racer I know. The amount of gameplay in this game is immense and it's presentation is flawless. The online option also makes it a significant game in Nintendo's history.