The artist formerly known as Captain B
Yo dawg, I'mma let you finish, but Link's Awakening had the best overworld.
Link's Awakening is, in many ways, very similar to The Legend of Zelda: The Hyrule Fantasy. Single-screen scrolling? check. Eight dungeons plus a Level-9? Check. Hell, it even had some similar sprites (Moblins, Keese, Keys, Link...). It helps that Tezuka came back to the Zelda team to work on this one.
That said, the overworld completely betrays THF. THF, as described by Hisak above, gave you nearly the whole world to explore from the start, and what it didn't give you was but two completely unconnected overworld screens. In a way, this kind of worked out even better.
The overworld broadens as you complete dungeons, up to the point that about midway through the game, you feel like you're very far away from mabe village, even though it's just a field and river away. I think it helped that Link's Awakening had a very strong mariner theme to it. Midway through, you gain pretty much unrestricted access to most of Koholint, and when reach places like Face Shrine and Martha's Bay, where water becomes increasingly abundant, you feel like you've traveled so far that you're at the edge of the world. Now there's weird crystals you need to dash through, teleporting toucan things in dungeons, a whole village full of animals and a desert next to them... even a mermaid!
The further you get in the game, and the further you venture from Mabe Village, the more interesting and diverse the game becomes, almost as if you are leaving home and visiting foreign lands, with foreign wildlife and customs. Again though, it's only a 16x16 screen overworld. That's the size of two THF overworlds stacked on top of each other, and all the really interesting stuff happens when you go east anyways.
Of course, keep in mind this is coming from a guy who lives out in central united states, Just between the heartland and the urbanized east half, chicago and beyond. I've never ventured out to, say, New York, let alone on my own.