I agree that I like non-linearity, but I don't see it as that much of a problem. After about the third dungeon, you could go to almost anywhere in the game. There are only two other areas, besides the dungeons, that you can't or aren't meant to get to yet.
Oh but you could even get deep into the Mountains before you even have the hookshot. It's called Dark World cheating. You could get to the Dark World basically everywhere, even in Kakariko Village and basically all the lands around it by use of the portal just one screen up from the middle of Kakariko. There's a way around this through the forest, so you end up on the other side of the fence - you normally have need of the Titan's Mitt for that. I'd love to cheat the game like that.
Same for TLOZ and nabbing the power bracelet before I beat any dungeon. The sweetness that is non-linearity, I swear by it.
Also, your mentions of Thieve's Town reminded me of when I forgot to get the Titan's Mitt and just went through the game like normal, trying to figure how to save the other dwarf and how to get to Misery Mire. I also thought I had to taken the Maiden out of the dungeon, and lost her, just like the first time I played OoT and thought I had to take Ruto out of Jabu-Jabu's Belly. >.<
Lol! I had the same thing with Ruto. I was *so* pleased with myself that I had managed to get her out. That's what she was so annoyingly whining about for god's sake! So I thought, the little lady will get what the little lady wants! But noooooo, that didn't play, so I had to go and find her
all over again *sigh*. The errors one makes as a game newb... It's quite shameless indeed.