Well, I guess I'll have to look without the ol' Nostalgia goggles here.
Recommendations
Majora's mask.
It's aged significantly better than Ocarina of time. It tells a daker tale, and has a much more involved and immersive world. The time rewind mechanic means many characters have a full schedule through the three days, the world never feels static, always moving. It's the greatest example of a persistent world in near any game, since so much can happen concurrently.
Banjo Tooie.
I see a lot of people going for Kazooie, but honestly the sequel is ten times better, and again especially, it aged better. Kazooie did it first, but Tooie did it better. It's huge, and open world, with plenty to do. Many of the worlds are connected in more ways than you think, and some of the level design is truly staggering even today. (Hailfire Peaks being the best example.)
Star Fox 64.
It's the best on rails shooter I've ever played, that's for sure. It hasn't been beaten since. It has some flaws (most notably no level select), but combat feels great. Deflecting lasers with your memetastic barrel roll, firing a well timed bomb into clusters of enemies, getting that ridiculously freaking hard medal... The standouts still stand out today.
Disrecommendations.
Donkey Kong 64
If someone recommends it, don't believe their scurillous lies. It's all nostalgia, that game was ass. It was Rare phoning it in, and it's weak sauce. Utter weak sauce. Just stick to the banjo games, and forget all about it.
Goldeneye.
Aged like meat left outside to rot. Just get Perfect Dark, way better game. It's aged substantially too, but it's much more advanced than Goldeneye. some of the level design and weapons are still pretty fresh today even, as well as the free form objective based approach. Anyway, next to PD, goldeneye has nothing left going for it.