I love sandbox-style campaigns. I can't imagine running a hack & slash railroad campaign again. No thanks.
That said, the best lesson I learned about running a sandbox campaign is that the "sand" is just as much about clues, hooks, leads, and rumors as it is locations. Actually, I'd argue that they are
more important than the locations themselves. Whereas a traditional hexcrawl is solely location-based, I like to run mystery sandboxes, where the players have to choose which clue to follow, not which point on a map.
In my experience, it's woefully inefficient to begin designing a sandbox campaign by creating a massive area map and filling in locations. That comes much later, and can even wait.
I start by brainstorming about what's generally going on in the region. Who are the major players and factions? What are their motivations and goals? What are the primary conflicts or sources of tension in the region? Who will the players interact with on a regular basis? Are there are any special or timed events that are going to occur in the near future? What are the rumors going being talked about locally?
Once that starts to take shape, I'll dive a little deeper and add some detail to the major NPCs. I'll start connecting the dots on their plans and how the NPCs might be connected to each other. It's especially helpful to think about what would happen if the PCs never get throw into the mix. After that, I'll try to come up with a secret for every NPC, major or minor. It's also helpful if the players do some of the "work" themselves and give you some basic background on their characters. Those can be mined for plot hooks as well.
During the brainstorm, I'll also come up with some unconnected leads and one-offs (side quests!) and locations too. Everything doesn't have to be connected, and the players figuring out what's what is part of what makes a sandbox fun. And yes, part of the initial setup is a map of the starting area and having some locations prepared. But again, I don't make that the focus at the start.
What's going to grab players immediately is choices. And I don't mean "left or right?" or "pick a hex". Choices will ultimately lead to a location, but the location itself isn't the driver (at least not all the time). When the players are unleashed into the campaign, whenever they talk to an NPC or discover a clue, it will lead to another NPC/clue/location, etc, etc. After a couple of sessions, ideally they'll have a few breadcrumbs to follow. Now you've got your sandbox!
Once I have a good idea of the goings-on behind the scenes, I come up with an initial hook that ties the players in. I try to make it have some personal connection to one or all of the characters. You want the players to have immediate buy-in so the upcoming choices feel important. It can be as simple as a letter from someone that needs help (family member?) or huge and sudden event that the players are pulled into (like a coup attempt!).
I'll also add that complications and events are great for mystery sandboxes. There's nothing like throwing a wrench in the players' plans and forcing them to think quickly and then make a difficult decision about what to do next, especially if they are on the clock.
It goes without saying that I borrow heavily from published sources, and the easiest things to repurpose are maps. That's one of the reasons why I don't spend much time up front fleshing out the details of locations.
Finally, I always refer people to this module:
The Beast of Graenseskov, written by ENWorld's own Quickleaf. It's an amazing example of a mystery sandbox. It has a
massive amount of content (maybe too much!) within a relatively small area. The players are quickly thrown into a mystery and get a ton of clues right out of the gate. Following up on those clues leads to others and to new locations, etc, etc. It's a textbook study in creating a sandbox campaign.