After putting a pitch to which the players agree - "Samurai + the mythical world of early 90s Hong Kong martial arts movies" or "D&D based in the world set out in the 4e books, and by the way every PC should have some reason to fight goblins built in to their backstory" - the players then build PCs. As part of this, they will create backstory - families, locations, religious details etc that then become incorporated into the gameworld.
As GM, I will also work out details of the gameworld - maps, but more importantly history and NPC organisations, antagonists, gods etc - which I will link to elements in the PC backgrounds. Some of this I will tell to the relevant player, some of this I will keep to myself for subsequent big reveals. This sort of detail can run from half-a-dozen pages at the start to dozens of pages by the end of a campaign.
I think the critical thing here is that you get the characters designed and then build the world around them.
That's another great approach. Not one I tend to choose as I don't really enjoy designing worlds. Too lazy

But I think we end up with the same thing - characters' ideas, goals, problems, obligations and NPC relationships (good and bad) built directly into the world.
Actually, in my experience, the 'ultimate' sandbox is the anathema of meaningful choices: Whenever players are free to do whatever they please, no meaningful gameplay is the most likely result.
I can't argue with your experience, but I think it's a pity you've reached that conclusion.
I think you're right to highlight meaningful choices though. Without knowing what constitutes meaningful choice for you as a player, I can't comment further.
However, in my initial example, I described a process by which the players themselves create the gameworld and then their characters in it. The idea is that meaning gets built in by the players.
Have a look at the situation that the two characters are in as the game starts. I'd argue they both have some very, very meaningful choices to make but with no way to predict what the situation will be tomorrow. What I think I can guarantee is that there will be a situation tomorrow, with more meaningful choices.