Si te gusta el SMash bros, el mejor es el de cube, además tiene muchos modos de juego para un jugador, el de N64 es jodidamente simple en ese sentido, solo tiene el modo arcade y los enemigos siempre son los mismos y salen en el mismo orden.
Como juegos de plataformas tienes muchos ademas del Mario 64:
DK 64, Banjo Kazooie, Banjo Tooie, Conker Bad Fur Day, Rayman 2, Gex, Glover, Goemon, Chameleon Twist 1 y 2, Yoshi's Story, Mischief Maker, Kirby 64, Tonic Trouble.
Otros juegos interesantes son:
Los de Acción de películas (Star Wars Shadows of the Empire, Star Wars Rogue Squadron, Indiana Jones)
Shooters (Goldeneye, Turok 2, Perfect Dark)
Los deportivos de Mario (Mario Tennis, Kart y Golf)
Otros juegos que quizás te gusten:
Shadowman, Jet Force Gemini, Blast Corps, Hybrid Heaven, Megaman 64, Castlevania Legacy of Darkness (no aconsejo que juegues al Castlevania 64 "normal") Worms Armageddon, Rampage World Tour, Rakuga Kids, Starfox 64 (Lylat Wars), Iggy's Wrecking balls, wave racer, excitebike 64.
Respecto a lo de Zelda yo no te aconsejo empezar con el Ocarina, es uno de los Zeldas mas tediosos que hay, a mi me aburre bastante, si quieres empezar con un Zelda, empieza por alguno 2d (El de SNES, los de Game Boy y el de GBA son mucho más aceptables).