Changing an element to make it 'better' would imply that the game needed fixing to begin with! But them, I'm a die-hard AoL fan as it was the first Zelda game I owned, and the only one I owned until OoT came out...
But my AoL bias aside, I think removing the overworld map would make the game feel a lot more claustrophobic. I still feel, in all it's 8-bit vagueness, that the overworld in AoL is the most expansive Zelda overworld. Hyrule feels HUGE, especially when you come across the even smaller version of the first games' map tucked in the south-west corner. Yes, the whole thing is really just consisting of basic field, forest, and mountain tiles, but it still feels like a massive world.
Finding the hidden side-scrolling trigger points on the map is truly some of the great secret-questing in Zelda games. Try playing without a walkthrough and go looking for heart containers or 1ups. But then, I come from an age where your companion to the game was a notepad of villager dialogue and graph paper maps.
People complain of too much hand-holding in Zelda now, but harp on AoL for being too hard or weird. The overworld may be daunting, but it doesn't make the game bad. I always argue that the game is only as bad as the amount of time you don't feel you need to put into it.