I prefer a mix of both. I often like the "levels" or the overall progress of the game to be linear, but I like those levels to give me enough freedom to make up my own strategies without being so open that I get lost or distracted. The Halo games are a perfect balance of linear and non linear. The missions follow a logical path so the story can be focused and compelling, but the combat can be handled who you see fit and thanks to the best AI in gaming it's never exactly the same.
So in that regard I like Zelda the way it is. In Zelda OoT you almost always needed one thing to be able to do another. Some times the game would just plan tell you that you had to do something before you could do anything else. But, at least with Zelda, it's not the order of the dungeons that matters so long as the overall progress though the story has a beginning, a middle and an end.
