This post is a long time coming.
I'll start off with a confession: before I got into OSR-style games, I had never really designed a sandbox before.
Oh sure, I'd designed campaign settings before, but always from a top-down, "all the big world building stuff first!" sort of perspective. This is precisely how to burn yourself out and make a bunch of shit that no one ever cares about or even knows about except for you. Talking about these things are the sort of DM equivalent of "let me tell you about my character" that make me shy away from gaming forums and disengage from folks who blather on about "In my campaign..." Nope. Done.
(I'll admit that I thought of metaplots that I wanted to run with and "designed campaigns" around them, too. Yes, I was a shitty DM.)
But those weren't sandboxes. They were thinly-veiled railroads. Once, during a tense negotiation between an NPC and the party, one of my players, irritated with the other players for fucking role playing, said "Guys, let's just agree, otherwise we won't get to the adventure." That shit stung. Like I couldn't handle it if things went off the rails. Maybe I couldn't, I don't know. But it was enough of a kick in the crotch that I decided I could and had to do better.
I can't say that I magically stopped being that guy and started being this guy. There was a transition along the way. Experiments were attempted. Sometimes there were mistakes. Sometimes victories. My Iron Coast campaign is filled with both. Parsing out which is which has taught me a lot about how I prefer to design a hexcrawl/sandbox/whatever.
First, let me say that I am not a "prep heavy" guy. I think I've made this point several times before. When I'm building a hexcrawl, I want that hexcrawl to be one that I can build things on the fly for. Sure, having a guide for roughly what's where and a guiding aesthetic that tells me what sorts of stuff to include is pretty important, but I'm not going to write out something on the scale of Carcosa or Isle of the Unknown. No "one or two predetermined encounters" per hex for me. Nope. I envy folks who can do that, but my brain just doesn't work that way.
Second, the 6-mile hex is king. Movement math works out better that way, as does time. Outside of the 6-mile hex, I scale up to a 24-mile hex and down to a 1-mile hex. Thus is the universe described.
When I was designing the Iron Coast map, I designed at a 6-mile scale. This was fine and all, but it ended up giving me a relatively small area that could have been much larger. The result is that -- to me, at least, I've not heard any players complain about this stuff -- the map feels cramped, with things together really quite closely. There's little to no buffer between things and an area I had imagined teeming with independent Orphaned Baronies is instead stuck with just a few.
I found myself liberated a bit when I zoomed in on the Iron Coast and started drawing in 1-mile hexes inside the 6-mile hexes (for folks keeping track at home, Black Blade Publishing makes an awesome 6-to-1 hex paper for just such an application). Now I could get a little more of the variation I was hoping for, but it's on a much smaller scale. Lesson learned.
Here's the process I use now: I start at the 24-mile hex scale and rough out an area, however large. If I want to give each hex some detail (like a name, "hey, there's a town in there," who the local lord is), it's pretty much for the whole area. "It's like this over here." Now, when folks go explore that hex, I whip out the 6-mile hexmap and figure out where things are on that scale. This allows me to drill down in detail, starting with "it's like this over here," then going to "these things are here and those things are there" and if I really want, I can zoom in even further to the 1-mile scale for "this is exactly how this thing is in exactly this spot." Start broad, work to fine, zooming in as events warrant and detail requires.