It's interesting to me that Bethesda and Rockstar games seem to be going in different directions.
What I mean by that is, to me, Bethesda's most recent games, Oblivion and Fallout 3, are even more sandboxy than their previous games.
In Morrowind, for example, the world didn't scale with you. What this meant was that you could technically go anywhere and do anything but in reality, some areas and some quests were best left until later.
This forced a certain level of grinding into the mix, or at least made tackling the game in a certain order the path of least resistance.
While making the entire world revolve around the character was disliked by some players, I loved it, precisely because it made Oblivion the Ultimate Sandbox.
If you look at Grand Theft Auto IV, by contrast, it's much less of a sandbox than previous GTA games, for my money. The game constantly prompts you (through the cellphone) to quests, to hanging out with your friends and so forth.
It's really interesting to see the two companies that (in my mind at least) really pioneered the true sandbox and watch one of them trying to find ways to make the game even MORE flexible, while the other wants to try and nudge you onto an optimal path.
And oddly enough, I think both strategies were winners for the companies involved. GTA IV had much more of a story and a much tighter, consistent feel. Basically, the more you walked that path the game tried to nudge you onto, the better an experience you had.
Meanwhile in Fallout 3, the game is often at its best when you pick a direction and just walk until something catches your eye, then investigate it.
While I've done the big quests many times, if I pick a direction and walk I *will* encounter something brand new within an hour or so. It might be a random encounter but often it's a place I've seen on the horizon but never visited.