I think the main problem with open world and sandbox games is easing players into the world.
And the problem a lot of the time is also having everything in the world be exactly the same.
First off Sandbox games should ease you into your god-like abilities. Give the player a chance to get a satisfying amount of playtime out of the game before it inevitably becomes boring, god mode is basically a fast track to boredom.
There should be layers to the environments too. There should be small areas like buildings, your own base, underground tunnels, tombs, whatever.
Cities should have a distinct layout, have a good use of both vertical and horizontal space and have landmarks. Oh and they should have plenty of secret areas too.
Then you have open aired environments like jungles and whatever that you should be able to travel across really quickly, should again have interesting landmarks and should be littered with secrets for exploration.
I think they should give room for roleplaying too. Enough flexibility to have the player create his own little events instead of always conforming to the games rules.
Things like vantage points, potential stealth features, vague sidequests, and completly random things that have absolutely nothing to do with anything!

I think GTA SA did some of the roleplay'y bit quite well.