LoZ, AoL, ALttP, Oot, MM, and PH let you do dungeons in various orders. Wind Waker is odd because a sizable portion of the main quest can be done in different orders but dungeons have a strict progression. Skyward Sword lets you do the Song of the Hero quest in different orders. The Four Swords games are nonlinear too I think but I don't play them. I really have a problem with how much linearity has been embraced by the game designers lately. Nonlinearity aids exploration and makes the games more replayable. Nonlinear dungeon progression basically adds a difficult puzzle to games for players to figure out. It's rarely presented to the player that dungeons can be interchanged. Figuring out what different orders are possible is its own reward because it can be challenging and requires you to think about things in a different way. Nonlinearity goes way beyond being able to do dungeons in different orders, and it encompasses being able to do other parts of the quest in various orders which can even involve the order you obtain items.
The best game for nonlinearity is probably ALttP because doing dungeons in an order other than numerically is actually beneficial in some cases and in others requires you to solve dungeons in novel ways. With ALttP you are missing out if you do the game the same way every time. My best example of this is how I figured out that you can complete the Ice Palace without the hookshot. You have to think outside the box and do the dungeon in a different manner than usual in order to pull it off, but it is possible. Also for nonlinearity within dungeons themselves ALttP is easily the best game. One fun game I like to play is figuring out how many leftover keys you can finish a dungeon with. Misery Mire is the craziest one in which there are six small keys to six locked doors, but you can finish the dungeon with 4 still in hand.
With Ocarina of Time I literally have spent dozens of playthroughs figuring out all the different choices the player can make. Other than for speedrunning there aren't many benefits for doing things in different orders in OoT, but I find it very fun just figuring out what is possible. Optional items also play into this- take the Bottom of the Well as an example. A player who has limited experience will think that you need to complete it right before the Shadow Temple, someone who has tried different things will realize that you can do it earlier as soon as you complete the Forest Temple, and finally a player who has really experimented with the game will realize that the lens of truth is optional and that you don't even have to do the Bottom of the Well. Once you know the basics of the game extremely well, only being able to do novel things will consistently be interesting.
For instance I've played Twilight Princess about 5 times, and every time you have to do the main quest the same way so now I'm pretty bored with it. Ocarina of Time I've played it at least 50-60 times and I'm still finding new things to do (and I haven't ventured into glitching yet either). It's just simply fun for me to do things that on the surface seem like they shouldn't be possible. For example I've obtained the Gerudo Membership pass before the hookshot (and with a minor glitch you can also get the Requiem of Spirit at this point too), obtained the medallions in the order Water-Forest-Spirit-Fire-Shadow without glitches, done the Fire Temple without the Goron's Tunic which requires you to have the longshot before the Fire Temple, and completed the Bottom of the Well after finishing all of the trials in Ganon's Tower.