To start off
The Platonically Perfect Sandbox would have the following characteristics:
1. The places are interesting.
2. The places are distinctive enough in the DMs mind that s/he can refer to them and think up details about them when they're off-screen. S/he knows what each one is "about". (This can be either because s/he is intimately familiar with them or because they are based on ideas s/he can grasp "This is the place that's like Vienna", "This is the lava dungeon").
3. Travel between any place and any other place involves going through another, equally interesting, place.
4. There are at least 2 choices about how to go on any trip and both/all are attractive for different reasons. There are, however, few enough choices that the PCs--as a group--can parse them.
5. Every place contains at least one good reason to visit every other place.
6. The NPCs are interesting, but--more importantly--each has as many connections (possibly hidden or through intermediaries) to the other NPCs as the players' suspension-of-disbelief will allow. (Practically speaking this number is very high since the players will probably not find out every connection for every NPC.)
7. There are enough locations and NPCs that the players don't exhaust them and new ones never have to be made up (the possible relationships are already latent in the places and people from the point of creation, meaning the DM never has to tweak), yet there are few enough that the DM can call them all to mind whenever necessary and the PCs--while not needing to be able to remember all of them--can keep track of enough of them that they basically know what's going on and can make decisions. (This is, in most cases, impossible.)
How I got there and some related ideas:
So I was thinking about how well this worked out.
Another Dispatch From The Department of Obvious:
When you're DMing, things you can remember are good.
Whenever you hear about someone rolling with Professor Barker or Ed Greenwood or some other pillar of the hobby, they always talk about how the person just seems to spin it all out, noteless.
This is because they know how the gameworld will respond to PC actions. Because they know the gameworld like the back of their hand (better, actually. How bored do you have to be to know the back of your hand?). Because they wrote the gameworld.
Those of us who do not have time to write an entire gameworld will take solace from the knowledge that these folks also know it because it tends to act like earlier analogues. Ed Greenwood knows Waterdeep because he wrote it but also because it acts a lot like Lankhmar which in turn acts a lot like noir-era Manhattan wearing Medieval London's clothes.
Details you can't remember and must write down are not bad: they often indicate (say, in a dungeon puzzle) a level of interesting complexity. However: the more you can remember, the more you can improvise, so rememberability is essential in a sandbox.
Here's a formula that's, again, obvious, but is useful to lay out at this point:
On any given game day, the value of whatever worldbuilding was done behind the setting you're using is equal to all the details you can easily access on paper for where the PCs actually are plus anything you can remember that day.
An example of often useless (in a game sense) world knowledge: the extended Cthulhu mythos in a Call of Cthulhu game. While conceiving the adventure it might be useful to know or have access to which Lovecraftian power has which modus operandi, but while actually running a given session at the table all you really need to know is what's going on with whatever single aspect of the Mythos you are trying to freak your PCs out with that day. Knowledge of offscreen pantheon (or panexodemoneon) elements doesn't come up much since Cthulhu is basically a horror game, not a game about magic and astral exploration. Usually.
An example of useful world knowledge in Cthulhu would be: knowing what the 1920's were like. Every single detail you have about the era--its politics, technology, social patterns--might come up if the PCs start getting creative. If you know the world, you can counter-punch confidently.
To some people, history is memorable to begin with and things that happen in real life constantly reinforce various historical facts ("Hitler was bad and his friends wore leather"), so it's easy to remember. History really all does weave together seamlessly so if you can manage to remember it you can get a lotta mileage out of it. A more interesting test-case of what makes a world-as-sandbox work is when the world is fictional.
As a thought experiment, here are some fictional things I can remember and how useful they'd be as templates to re-skin for use as D&D sandboxes or (more likely, at least in my case) parts thereof:
-The basic Lord of The Rings set-up. Not as useful as it seems at first because many interesting things about it are already integrated into the game (dwarves v. halflings for instance) and most of the other relationships are so powerfully centered around the central Evil Empire Vs. Everyone conflict that most locations don't relate powerfully to anything but that. Exceptions: Gollum is swipable (creepy NPC wants magic item even more than you and the Big Bad do) as is Denethor, the steward of Minas Tirith (NPC in temporary control of an important place doesn't want to give it up and is father to two PCs or good NPCs).
-Lunar: Silver Star Story, the video game. Very useful because the games's made up of a set of "themed" areas that are interconnected in ways that are pretty easy to remember if you played the game as well as several broadly-drawn NPCs that likewise are all inter-related. Plus it's already a fantasy setting. You can take the idea of like "High Priestess of a local vanilla religion who turns out to be a member of an evil humanoid race and ally to the big bad" and every other element in the setting has a relationship to that built in.
-1001 Arabian Nights. Not so useful because really no-one in the stories is connected to anyone else and no place is connected to any other place. It's full of good ideas, but none of them automatically imply any others.
-Alice's Adventures In Wonderland & Through The Looking Glass. Kinda useful because I can remember the "schticks" fairly well but limited because: 1-Most of the problems aren't "weaponized" (like, the Mad Tea Party is great, but turning that into a D&D scenario is as complex a problem as simply inventing one from scratch)(which problem you see graphically illustrated in the Dungeonland module whose solution is: everything is a monster you fight) 2-The relationships are fairly simple: everyone either works for a Queen or escapes her notice. Outside the opening shrinking/growing chapters, the geographical relationships aren't interesting.
-The original Star Wars. Somewhat useful because, unlike LOTR, the relationships aren't solely built around the Empire vs. Everyone axis. Like if I said "Do an adventure that's basically a fantasy version of what happens on Endor" you could pretty much write that adventure yourself: PCs sent to sabotage baddies in their base, notice or are noticed by superstitious natives, must recruit natives to help them (or succeed despite them). If I say "Jabba the Hutt but in the Middle Ages" you've got a bad guy, his characterization, a location (with a trap, a kind of monster, and some of the map), an environment, a plot (revenge against your party's rogue). However, unlike in Lunar, Jabba and the Ewoks aren't really related to each other.
-Game of Thrones. Semi-useful. The locations are really just based on real-world analogues or familiar fantasy archetypes, so they don't provide details you wouldn't have already like: how would a random encounter in King's Landing be different from one in Lankhmar? Exception: maybe The Wall. The castles are interesting but not, mostly, in a this-dungeon-is-unlike-that-one sense. The NPC inter-relationships are kinda useful but half of them are fairly good guys with uncomplicated desires, which doesn't give a DM much to go off of in terms of adventure fuel. The "bad half" of the cast is pretty good. If I put on a random encounter chart: "this NPC is basically Cersei Lannister and everything that implies" you basically got a whole gob of plot to play with, plus several NPCs with reasons to do things. Provided you can keep it all straight in your head.
-Shakespeare. Inter-relationships: good. Geography: bad.
-Superhero comic books: Most comics I can think of have simultaneously too many and too few relationships between characters: like Doctor Doom has been both ally and foe to Reed Richards many times but basically one's bad and one's good and that's that. They're probably related by marriage somehow at this point if you count future continuity, but not in any way that seems actionable over-all. The good guys are all allies, the bad guys are (often) all allies. The thing to do would be to zoom in on one story arc and use the relationships there. The individual bits of geography in comics are interesting, but movement between them is not really an issue so there's nothing to build a sandbox structure out of.
-Fafhrd/Mouser stories: inside Lankhmar they're useful, ones outside are less useful.
-Zork: Hardly any NPCs. The scale is too small--basically what you get in a Zork game is a single dungeon. Not much to base a "how this world would react" algorithm on.
Ok, so taking a look at all this, the ideal "rememberable" template for an open D&D world would be:
1-It matches the requirements at the beginning of this post as well as possible
2-It has conflict, but the conflict isn't just along an axis where all the good people are lined up against all the bad ones
3-It's got pre-modern technology, so that: 1-movement between places can't be instantly negotiated by airplane or starship and 2-the obstacles don't require a lot of "translation" in order to be usefully D&Ded
4-The DM is familiar enough with it to remember it all
To me, most published RPG settings don't really fit. They are so worried about making the world real-seeming enough that they don't provide adventure fuel. Places are hard to keep straight ( like I know in real life Ottawa is a lot like Philadelphia but in a game I need them to be different, travel from location to location is barely considered (even in something like the Majestic Wilderlands, most routes between points of interest in a given area basically present similar challenges), connections between places are generalized beyond usefulness ("Dorkendale is a major trade hub for the area south of the Scrublands".
What does fit is--maybe not that surprisingly--video games. Even something simple like Super Mario Brothers punches way above its weight class here. This is what I can remember from the first game:
you start above ground
then go into a fungus-infected dungeon
the dungeon can lead to an ocean but also has 3 connections to other places, one of which is sort of Halloweeny and I can't remember the others
proceeding by the most direct route across any place gets you to a lava dungeon, one of which has an eternal-loop puzzle
there's a princess who is moved from castle-to-castle by the big bad, she is allied with fungus people
there are also cloud cities accessible via beanstalks in certain places
That's already more rememberable adventure fuel than I got reading all through the entire Forgotten Realms set. And that's just what I remember without looking at the game. Imagine if you actually went back and played and drew a map. Or, perhaps more to the point, played the Super Mario RPG and remembered that.
Maybe this seems like a depressing conclusion to you: computer RPG environments make better templates for sandboxes than anything else out there. I don't think it should be, though. The Fortress of 10,000 Mists can still be as weird or literature-damaged as you need it to be, the only thing it's borrowing from Cloud World is the plumbing. As long as it doesn't leak, who cares where the plumbing's from?