This is what the overworlds have been until OoT came in and ruined that. Hell, until PH and ST, the 2D overworlds were still like that.
No they weren't. The overworlds in LoZ and ALttP were open and could be freely explored for the most part. They didn't impose tedious tasks like "search for a bunch of scrotum-shaped creatures in a maze-like forest" on you before letting you advance. In ALttP, as soon as I beat the starting dungeon, I could freely walk from one extreme of the overworld (Lost Woods) to the other (Hylia Lake). I could explore it and discover stuff like hidden caves, heart pieces or secret items and upgrades, on my own.
Contrast that with, say, SS's Eldrin Volcano, in which you had to continuously plod through a maze, alternating between dousing for stuff and solving puzzles in order to advance. You weren't exploring it, you were just performing mandatory task after mandatory task. And you certainly couldn't walk from one extreme of the world to another, not only because they had the brilliant idea of fragmenting it into three parts, but also because of how overly linear and scripted everything was.
Quit the opposite. The games have been getting longer, but much more emphasis has been placed on the overworld than when the series started. In LoZ, dungeons take up 2/3 of the gameplay in an 100% run. By the time we got to TP, Dungeons only took up a mere 50% of a main quest run. OoT changed the concept of what an overworld was. Instead of being a dangerous wilderness where you had to fight your way to the next dungeon, it was a boring, barren large empty area with much fewer barriers than its predecessors.
MM made the overworlds slightly closer to their original counterparts, but was still in the same vein as OoT's. The game increased dungeon length significantly, but still focused more on the overworld. tWW had more dungeons than MM, but less than what you would expect from a proper Zelda title. They kept MM's length, but put more focus on the overworld yet again. TP, despite having a full set of dungeon and with proper length, added a lot of overworld sections. Like MM, nearly every dungeon had an overworld section preceding it sans Hyrule Castle.
Before OoT, overworld segments were rare or completely non-existent. Once you beat a dungeon, you made your way to the next dungeon. The overworld has its own challenges and its own side content, but it behaves like a dungeon and you won't spend too much time here. And while I wouldn't say overworld segments aren't bad (for the most part) the massive increase in overworld size is. Because when you aren't engaged in an overworld segment, you're simply traveling to the next area and since the overworld is much more open than it originally was, the developers can't really offer challenges for you. You just wait until you get to your destination. This basically pauses the entire game for an obnoxiously extended period of time. It takes all of the joy you could have with exploration and makes "exploration" nothing more than a tedious long car ride.
No. In old games like LoZ, you had to explore the crap out of the overworld, looking for hints and secrets everywhere, in order to find the next dungeon. Though I guess if someone just follows a walkthrough and rushes from dungeon to dungeon, they wouldn't understand. But any person who played the game without a guide would spend most of their time exploring the overworld, whether they wanted to or not.
ALttP may have forced less exploration, as the player was told the locations of the dungeons from the onset, but the big explorable overworld was still there as an option. That's the way it should be as far as I'm concerned -- keep most of the overworld content open and optional.
OoT didn't add more "overworld segments". It had the smallest overworld in the series for its time, and the adult half of the game had you rushing from dungeon to dungeon with very little content in between. The child part had more out of dungeon gameplay, but most of it consisted in story segments, not overworld exploration.
As for TP, the overworld was big but empty and there was very little exploration, given the game's linear structure. I'd say the gameplay was about 50% dungeons, 40% story segments, and 10% exploration.
TWW was the sole exception, presenting the player with a huge overworld filled with content to discover. Too bad you couldn't explore it until reaching the second section of the game, but at least the first section wasn't very long.