I do like the idea, but I'm not sure how it would play out. I know I personally like to go around Zelda games, talking to everyone, looking at every piece of dialogue, every minute detail until I've found all the little things Nintendo has to offer. So if we got to choose our own fate, I would have difficulty choosing which path to take.
The best balance when considering this possibility would be a game that is, for the most part, linear and similar in its paths, but it diverges at certain points. Say you start out at a common point, then there's a decision to be made and the road splits in two. However, as you go through those paths, both bring you back to a central point again that MUST happen in order for the story of the game to progress. Then at another point, you may split onto two paths again and converge back when it comes to the final boss.
I agree with a point made earlier in the thread - this shouldn't be a main series game. More of an offshoot. But not so off as, say, Tingle Rosy Rupeeland. =P
