1. Goldeneye
2. Zelda: Majoras Mask
3. Starfox 64
4. Maro Kart 64 (Best played with friends).
5. Mario 64
6. Sin and Punishment (if your willing to import)
I would also like to note a few things:
1. Dont get Perfect Dark if you get Goldeneye, or vise versa, as they are virtualy the same game (some of PD's levels are 100% replicas from those in Goldeneye for crying out loud!). The main difference is the theme, so chose which you get based on which type you'd rather play: sci-fi world or secret agent durring soviet times. Oh, and yes, you can all commense to flame me now for saying thier too similar sense I know that alot of people will want to defend PD.
2. If you have a Gamecube you might want to get the version of Oot for that instead as its easier to come by, has slightly better grafics, and will probably cost less, then the Nintendo 64 version.
3. Super Smash Bros is a wonderful game, but its sequil is better, so get that instead.
4. Both f-Zero and Excitebike got mixed reviews when they came out, thus I wouldn't call them AAA titles. The new F-Zero GX(i think thats what its being called...) is looking quite good though, try that if you want F-zero goodness in 3D when it comes out.
5. Also, I wouldn't call it a AAA game, but Diddy Kong Racing was a game I found to be alot of fun back when it came out.