I'll add another thing to my sandbox thoughts. My ideal is something reminiscent of the old Quest for Glory computer game (originally known as Hero's Quest, before Sierra got C&D:ed by Milton Bradley or something).
The whole game is set in the Barony of Spielburg, a small alpine valley. This valley is beset by numerous problems: the Baron has been cursed by the witch Baba Yaga, his two children have disappeared, bandits and goblins roam the valley and are threatening the village. There are also smaller problems, like the village healer having lost her ring. Some of these issues are posted on the notice board at the Adventurer's Guild, others come up in conversation with various NPCs. You are able to explore the surroundings to your heart's content, though some places are a bit too dangerous without proper preparation and experience. The valley has many interesting places, and many interesting NPCs. There are some tasks that must be completed in order to win the game, and some that are just bonuses. Most tasks can be approached in several different ways, depending on your character's skills - or at least the sub-tasks required to complete the task (e.g. in order for the healer to brew a particular potion, you need certain ingredients. The ingredients would remain the same, but you could use different methods of acquiring them).
THAT'S what I mean when I say I would like a good sandbox adventure/campaign. A smallish area, a bunch of problems there that needs (or at least wants) solving, a bunch of things with which to solve them, interesting locations, cool NPCs. Ideally, many of the problems should have multiple different solutions, and some of the problems should be connected to other problems. The closest thing I can recall seeing in D&D is probably the first part of Night Below.