Another little odd game someone may have left out...
Hybrid Heaven. This was a decidedly odd game. It had some of the presentation style that Metal Gear Solid did, but is essentially an RPG wrestling game with a sci-fi plot. It's REALLY hard to describe, but I enjoyed it for the time that I played it. Just don't go with the hi-res mode, the frame rate tanks and makes it darn near unplayable.
Someone else already suggested Perfect Dark, and I agree with the choice. Great game. My brother likes it tons more than Goldeneye.
The Killer Instinct game was pretty decent, too.
Oh yeah, and Rogue Squadron and Battle for Naboo are two of the best Star Wars flight games ever made.
The second Castlevania game for N64 was not NEARLY as bad as everyone says, I enjoyed it immensely. It was what the first one should've been.
Lastly, play some Ogre Battle 64. Great, great strategy game there. And it has a very mature, FF Tactics style storyline.
That's all I can think of right now. I'm sure there's more, but I tend to go for something as long as its good, regardless of the kiddiness. Which makes me recommend Paper Mario.

And I can't understand why so many people love Tetris so much... *Sarge braces himself for flaming retribution* Guess I'm too much of a RPG / action / fighting weenie. Although Mario Picross is really good stuff for the original GB.

Sarge out.