The old games I would recommend:
Portables:
- Minish Cap on GBA (Great storyline and fun characters, very fun puzzle solving, although the first boss makes you want to slap people)
- A Link Between Worlds on the 3DS (not a long game, but very accessible and has very fun puzzle solving mechanics - although sometimes you need the 3D to understand how to solve a puzzle. Fun characters too!)
- Ocarina of Time on the 3DS (a classic that still works for a lot of people. The water temple is no longer a tedious drag (or so I've heard from N64 vets)
Classic Gaming:
- A Link to the Past on the SNES/virtual console on 3DS (very great gaming. People say that A Link Between Worlds feels like it's a more polished version of this! I disagree, but I like the new game better)
- Link's Adventure 2 on the NES (sidescrolling, weird version of Zelda. Still fun, but HARD as hell. I recently completed this with help of save states.)
- Link's Awakening on GBC/virtual console on 3DS (slightly wonky mechanics, but fun!)
I have to say, try out Majora's Mask on the 3DS. Some people like the time mechanics, I did not. LoZ was always about clearing dungeons, getting the next key item and then using the key item to clear more dungeons. Having the time reset, as well as everything made me want to pull my own hair out - it felt fruitless.