The first time I played through Ocarina of Time, it took me forever to figure out that you had to hookshot the branch to enter the Forest Temple. I probably searched the entire overworld trying to find a way to repair the broken stairs. I actually discovered it by accident while looking for hidden Hookshot targets.
The first time I played Twilight Princess I got stuck for hours in the Lakebed Temple. What is obvious to most people was definitely not obvious to me. Midna gives hints about the stalactites hanging from the ceiling, but I had no idea what a stalactite was, and I had no access to Google at the time. Eventually, I noticed that they looked like they had "weak spots" and tried using bomb arrows on them, but it did take a very long time and I nearly gave up.
Back to Ocarina of Time, when I first tried getting the Biggoron Sword, I didn't know about the Trading Sequence. I found Medigoron in Goron City, and bought the Giant's Knife off him, but it broke. So I bought it again, and kept buying it, thinking that was how to obtain the Biggoron Sword (I thought after several failed attempts, he would eventually perfect the sword). I wasted a lot of time going back and forth from the Market to Goron City to collect rupees. Several hours, at least. Not exactly my proudest moment.
And lastly, the first time I played The Wind Waker, I had no idea how to get the sail, so I probably talked to every single NPC on the island, including Zunari, who I initially said no to because I didn't realize he was trying to sell me the sail ("That" is not very helpful). Luckily it didn't take me too long to finally give in and buy "That" from him, but it was probably the third time I had talked to him after making at least two laps around the island talking to everybody.