I'm starting to realize why non-linearity is not overly practiced, there is just so much complexity that it's almost best to avoid non-linearity altogether.
Not necessarily; it just depends on how your game is designed. There's a common conception that nonlinearity = good and linearity = bad but this isn't true. A screwdriver is good for screwing in a screw but bad for hammering in a nail, and vice versa for hammers. It's about selecting the right tool for the job, or in the case of adventure game design, selecting the right medium for the story (see edit below).
Where I think most people go wrong is that they want to make a Zelda game (which almost always follow a linear narrative) but they want to make it nonlinear because "player choice is awesome you guys!" Player choice is only awesome when that choice is meaningful - it's why I abhor games that give you a "choice" but don't go anywhere until you pick the right one (e.g. Zelda asking Link if he has the Kokiri's Emerald in OoT). But that's a bit of a tangent. I was going to go into more detail about "nonlinearity" being PZC shorthand for "You can do the dungeons in any order" but I don't want to turn this post into an essay.
Back to your original idea though, I think adventure games are best when exploration is rewarded but not enforced. For example, in the Deku tree there's a bombable wall that you can't do anything with until you progress further into the game, behind which is a gold skultula and maybe some rupees or a heart piece or something - things that aren't essential to the game's narrative but reward the player. What you're suggesting is putting the Kokiri's Emerald behind there, forcing the player to return later. Given that the Emerald doesn't actually do anything besides advancing the plot it's not even rewarding to uncover that room, it's just shit you have to do. If I remember correctly, in my ancient quest Hero of Time every dungeon had a HCP in plain sight but many/most (maybe even all?) were inaccessible with your current gear. This wasn't the best idea as there was often no point returning later besides collecting the heart pieces. It was rewarding completionists more than explorers, but at least it was optional.
EDIT: Just realised I went off on a tangent and never talked about when you should use a screwdriver and when you should use a hammer, so here goes:
If we take the original LoZ, the plot allows for a very nonlinear playthrough (get the 8 McGuffins) but the nature of the game doesn't. In Zelda, progression goes hand-in-hand with strength. Every boss leaves behind a heart container, heart containers allow you to get stronger swords, and you gain a larger arsenal as you play - including rings that boost your defense. This is very satisfying for the player as they can clearly see themselves growing and becoming stronger as they complete more of the game (and they even show this on the select screen), but if the dungeons were designed to be done in any order they'd either need a consistent, easy difficulty (which isn't compatible with Link's growth) or the difficulty of all the dungeons would need to grow dynamically with Link's strength (like in The Elder Scrolls). Having numbered dungeons - a suggested order - was a great compromise. It was nonlinearity with a linear guide.
When most people attempt "nonlinearity" in ZQuest they either take the all-dungeons-have-equal-difficulty option (because dynamic difficulty would require scripting and stuff) or make it only half nonlinear, with linear blocks on nonlinearity (see Koh's post). This works better than full nonlinearity because consciously or not the creator understands that the nature of Zelda games, where progression = strength, is fundamentally incompatible with unordered dungeons. In order to ensure the player doesn't get TOO strong for the game they have to limit the choice to within discrete blocks of similar difficulty - either having them consistent (so accounting for Link's growth the first dungeon is slightly harder and the last dungeon is slightly easier) or having a suggested order (where the difficulty/difficulty curve is consistent IF you take the suggested route, but it's not necessary to do so). The main benefit to this segmented approach over LoZ's "linear guide" approach is that it allows the game to have a more structured narrative. It's easier for the designer to know exactly where the player will be at a given point in the game, making it easier to deliver a coherent narrative (e.g. when you first meet Zelda in OoT she/the game assumes you have the Emerald because ordinarily to have to get it in order to meet Zelda, but if you glitch the game and see Zelda without ever hearing anything about the Emerald that part of the narrative suddenly makes no sense). Also, narrative doesn't need to be delivered in cutscenes - that was just an example. Something like opening up the Dark World in LttP is a change in the narrative that wouldn't make sense if Link hadn't gotten the Master Sword and fought Agahnim.
So there you have it. If you're going to make a quest in the vein of Zelda, where game progression is reflected in the strength of the protagonist, you can't just lay down an overworld with half a dozen equally difficult dungeons for the sake of "nonlinearity". That breaks your game - the two things are incompatible. You have to change one thing to fit the other, by either having Link NOT grow stronger (no heart, sword or ring upgrades, no weapons that drastically benefit the player (e.g. hammer)) or nudging/guiding the player along a suggested route (hard enemies to dissuade the player from entering areas they're not ready for, numbering the dungeons, requiring certain items to progress, etc.).
I think it's also fun to reward the player a little bit for going outside the guide, to encourage that exploration. It's not hard to find items that are quite useful in the early game but lose their efficacy in the later game (the boomerang is a good example, despite it still being pretty useful later), so provided it's not game breaking it's good to have these items barely in reach of the player at the time they could really benefit from them. They should never need to get it but should they decide to stray from the path into more dangerous territory there should be something worthwhile for them to find. If all there is to find is, for example, monster bait or something, and there's no point before that place in the guide where it's useful to have that item, it was a waste of time for the player to endure that adversity early on in the game. They got nothing out of it. Oh! A good example of this done right is the power bracelet in LoZ. It's in a fairly difficult region of the overworld but having the ability to quick-travel as early as possible is advantageous - it's worth going a little bit beyond what you're prepared for to acquire. It's also why the white sword and blue ring are guarded by more difficult enemies.
Anyway, enough ranting now. Apologies to everyone that had to sit through that. 
Edited by NoeL, 06 April 2014 - 11:59 PM.
