Celebrim
Legend
Assuming the sandbox is supposed to emulate the sort of adventures seen by Conan, or Elric, or Fafhrd and the Grey Mouser, I'm not sure that's necessary (if it's done well). One of the feature of their adventures is that wherever they went there was adventure to be found.
There is another way to look at this. By the rule that any story about a hero is only a story of the most interesting chapters of their life, we aren't actually hearing any of the stories of Conan not having adventures. That isn't to say Conan has no down time. Conan has many adventures, but the short stories we have span probably 40 years of his life. Conan actually only has an adventure or two per game year, and the rest of the time is more boring 'down time'. Granted, some of that down time is somewhat interesting stuff like being a pirate, being a soldier, or ruling a kingdom but generally we pick up the story of Conan as some less interesting chapter of his life is coming to a close - he's been ship wrecked, he ran out of money and needs a new job, he's minding his own business in a new job when a naked woman suddenly throws herself at him and begs his protection, the nation he's been fighting for is defeated in battle or won't pay him, he's enduring a coup or assassination attempt, and so forth.
If we assume our sandbox is something like a Conan sandbox, we'd be justified in hand waving away long stretches of game time until the PC's find an adventure (or it finds them).
How dense you want to make the sandbox is something you can control with frequency of random encounters or random events. A good sandbox is capable of generating or suggesting context to a random event, and a good DM will eventually try to link random events to ongoing themes or prior encounters. So you don't actually need as much density as an encounter in every hex. What you do need is enough understanding of the setting to have an idea what this random encounter means. A good example of that on a micro-scale is the random encounter tables in the old Judges Guild module Caverns of Thracia, where each random monster was linked to some lair in the dungeon.
You don't need to go that far, but you do need to have an idea why the random encounter might be in this location, what their goals are, whether they have a lair, how far it is to the lair, what knowledge the creature may have of the surrounding area. Create backstories on the fly, and start populating the 'empty' hexes as needed. Yes, that means that you can improvise new content as needed, but it also means that the more you know - the more islands (or continents!) of content you have already created in your ocean - the more granular and interesting your new content is likely to be and the more sources of inspiration you are likely to have.
Random doesn't have to mean arbitrary and disconnected from the rest of the setting.
I'd also suggest that until the PC's are immersed in the setting, you are fully justified to engage in some artful railroading techniques. If there is ever a time to offer railroads up, it's early in the game. You can make the initial setting a very detailed 'small world' with an initial mini-campaign. You can give the player's false choices - the 'Desert of Desolation' campaign begins with one that can be made more artful with a bit of effort. You can make judicious use of Schrödinger’s Map so that those islands of prepared content that help orient the players and get them involved are found regardless of the hex they step into. It's perfectly ok to have a 'fixed' encounter keyed to the "third desert hex the players enter", or "the second time they enter a this city", or "if the players travel 1 day to the north".