The Legend of Zelda video game for the Nintendo Entertainment System was the first game to introduce a save feature and the ability to explore the game world in any order you wished. It was the first Sandbox, a term that has a different meaning in tabletop pen and paper role playing games than video games.
Traditionally in Dungeons and Dragons, the sandbox is a large area that the players are free to explore as they see fit, but it is much more than just that. The term is often used as the opposite of the oft-dreaded "railroad" type game. In a railroady-game, the DM often just shuttles the players along from plot point to plot point to tell his or her story, whereas in a sandbox the players are given some points of interest to explore and allowed to do as they please.
What is special and unique about the Legend of Zelda sandbox is how it grows naturally through the course of the game, with more and more of it becoming available as Link conquers dungeons and acquires magical items that allow him to explore more of the world.
In A Link to the Past, this often took the form of a physical barrier such as a giant rock blocking a path. These were typically things that any clever D&D player would be able to circumnavigate with little difficulty, and as such, strains the bounds of verisimilitude as well as player credulity. The real world simply does now work that way.
My personal favorite method of unlocking more and more of the Hyrule Sandbox came in Twilight Princess.
In Twilight Princess, there are several large bridges that, at the beginning of the game, are broken and displaced to other areas of the world by the evil Darkness that has swept over the land, and at several points in the game it is required that a bridge be repaired to move on to the next part of the story.
Bridges are important to people. Their construction often inspires awe and creates an easily used path where there was only an obstacle before. A bridge enables commerce and communication between peoples on either side. The lack of a bridge causes delays and detours.
So, my suggestion to DMs out there is to make good use of bridges! Place one in a strategic, important place. Especially during the heroic tier in 4e, when players don't have much in the way of flying capability. Maybe one of the PCs has a relative or ancestor who helped build it. Make sure they use it numerous times by placing various MacGuffins on either side of it. This also helps the players see how the bridge helps the communities on either side of it. Perhaps one side depends on the other for foodstuffs, while the other side requires minerals or other raw materials.
Then, have your BBEG destroy it, preferably to facilitate an escape, while simultaneously causing all manner of hardship and suffering for the many people who depended on that bridge for commerce. Make it as dramatic as possible. Done right, the violent and deliberate destruction of any important landmark such as a bridge or even a statue can be just as world-changing to the players as the death of a relative or friend, and possibly more so if they have come to have a degree of respect for how important such a landmark is to the population at large.