If you enjoyed the Mystical Ninja/Goemon series for the SNES then you'll love Goemon's Great Adventure. Its an excellent 2.5D action/platformer (y'know... 2D gameplay but 3D graphics like Klonoa, Pandemonium..etc) with lots of gameplay, nice graphics and music..etc.
F-Zero X is a nice game for the N64 as well. Doom 64 is a pretty good version of Doom.. totally different levels and it has a nice look to it. Paper Mario is a neat action/rpg game with nice graphics. Not sure if you'll like it though.
Sin and Punishment is a hard to find japanese N64 game...its best to find the rom and play it on an emulator. Its too bad it never left Japan.
WaveRace 64 is pretty cool.. I'm surprised there aren't more water racing games with dynamic water effects are out there.