For the more prevalent Zelda formula (get item that lets you do dungeon that lets you get to next dungeon to get new item), I'd recommend Ocarina of Time or Wind Waker.
Ocarina of Time is timeless largely due to it's more generic themes (save the princess from the big bad by beating the generic element temples), but it has a mature, brooding atmosphere to it that no other zelda game has really captured imo. The dungeons are still some of my favorites in the series, and I love a good time skip mechanic. It's impossible to go wrong with it really, I don't think there are many people that would argue it's a bad game, just overhyped (which I'd disagree with personally).
Wind Waker is one of the more unique entries, and it's probably my second favorite Zelda game. Again, it follows that basic formula, but there's a greater emphasis on exploration. Sailing is done pretty well, dungeons are solid, and there are fun characters to meet. I do recommend playing the Wii U version if possible though, as it makes one of the more obnoxious parts of the game far more enjoyable.
If you don't like how limiting that formula is, play BOTW. It's a completely different game from the rest in the series. While I like that game a good bit for what it does well, it's deceptively shallow and contains the least interesting dungeons in the series (though it's filled to the brim with mini-dungeons, so to speak). I don't think they did a good job reinventing the dungeon loop aspect of the previous entries, but they knocked it out of the park with exploration. So if you really think the dungeon formula is what makes you dislike Phantom Hourglass and not just the quality of the dungeon formula in that game, then play BOTW.
That said, the only non-handheld Zelda entry I absolutely recommend against playing is Skyward Sword. At least I recommend against starting with it. It's not awful, but the game treats you like a 4 year old the entire time, and even if you set that aside, there's an awful lot of backtracking (not in a fun way). Also, I personally found the motion controls maddening.
