It might be a bit ironic for me to complain about sandbox-type games after complaining about utterly linear games, but the exact opposite of a bad thing isn't necessarily a good thing itself.
The idea of a sandbox-style game (with truly free movement) is rather exciting in theory. Nothing is more irritating than having absolutely stunning scenery in a game around you, but nevertheless being artificially confined to an extremely narrow path from which you can not deviate, no matter what (usually impeded by the most ridiculous obstacles). As a computer gamer from the 80's and 90's it has always been a wet dream to be able to just take a random direction in a game and start walking there, just to see what's there, without being confined by artifical obstacles. In other words, a game world which resembles the real world in that you can just go almost wherever you want, always finding something different and interesting.
Of course in the 80's and 90's the technology was the largest obstacle stopping games from supporting this. While more or less "sandbox-style" games have always existed from the dawn of computer gaming (from all the way back in the time of text adventures), they were still limited by technology (eg. to be sprite-based 2D games, where there was no real joy in exploring your surroundings like it would be in real life). You could explore the world freely... but it was just a 2D world made of sprites (or in text adventures, consisting of just textual descriptions). Not all that exciting.
Some 3D games of the 90's tried to delve into sandbox-style gaming (such as The Elder Scrolls II: Daggerfall), but limitations in 3D technology meant that the experience was rather underwhelming (poor graphics, repetitive and poor scenery, and so on).
Flight simulators were one game type of the 90's (and even the 80's) which explored this concept more profoundly, but they, too, were quite limited by technology: Usually most of the world was just completely flat, with extremely low-resolution blocky textures. Only some major cities had actual 3D objects, but they were also quite primitive and didn't really give the feeling of a natural-looking world.
It was not until well into the 2000's that technology was advanced enough to allow a true sandbox experience in 3D from first-person perspective with beautiful and realistic graphics and geometry.
The Elder Scrolls IV: Oblivion was one of the first major and most influential games of this type (and basically the first one I have played of this type). Playing the game for the first time was a marvelous experience: Not only were the graphics absolutely gorgeous (at least by 2006 standards), but you really, truly could just wander off to any random direction and just keep walking and walking, and there would always be something different there. What's more, the terrain was superbly realistic and natural-looking, with no sense of repetitiveness: Every tree, rock, hill, river and lake was unique and very natural-looking. You could wander along plains, dense forests, high snowy mountains, or take a dive in a lake and explore its bottom. And the outworld was just huge. It's the closest thing you could get to hiking for real.
The technology was still not absolutely perfect, as you would still get loading pauses and visibly changing levels of detail (even at the highest quality settings), but it was really close. (Newer games of the genre have polished out these annoyances and got rid of them almost completely.)
This was really the 80's gamer's dream come true: No boundaries (except for the outworld's very edges), free exploring, non-repetitive natural-looking beautiful scenery on an absolutely huge outworld.
So why am I complaining here? Isn't this exactly what I have been dreaming for two decades, and the perfect answer to my complaint about utter linearity in modern computer games?
The problem with modern sandbox-style games is that, quite sadly, the experience gets old quite fast. Free boundless exploring is great for a week or two, but after a while it gets a bit boring. The initial amazement at the new experience passes, and what you are left with is disorientation and a lack of goals. Free exploring is not that fun anymore after a few weeks of doing it.
This isn't a problem if the game gives you clear quests which you can complete.
The problem is, ironically, that if what you want is to complete the quests, the huge outworld is actually getting in your way. The longer the distances you have to travel and the more you have search for your destination, the more exasperating it gets. With the first few quests this isn't a problem, but after a dozen quests it starts getting bothersome and outright boring.
As I said earlier, this is in theory a great thing because it gives a sense of realism: In the real world you also have to travel great distances in order to get to places. However, from a gameplay point of view it can become a hindrance.
For this reason most such sandbox-style games offer a quicktravel feature to places you have already been at (just having to provide such a feature should be a big hint that there's something inherently non-working in the idea of a huge sandbox world; the quicktravel kind of defeats the purpose).
Having a huge outworld which can be freely explored without loading pauses and visible changes in level of detail seems to be a pet technological challenge for many game companies. Many companies are bringing their own sandbox-style games. Sometimes the sandboxing is done even at the expense of offering quests which keep the player interested in the game and focused at the goal.
I would have never thought 5 years ago that I would say this, but I just find these 3D sandbox-style games boring. Oblivion was just a wonderful and great experience, but sadly it immunized me against sandbox games. I don't find them exciting anymore. On the contrary, I feel that the sandboxing is somewhat detrimental to the game.
For example, Far Cry 2 is a sandbox-style game, but its quests are repetitive and boring. It doesn't succeed very well in keeping the player interested in the game for long. It feels like the developers concentrated too much on the technology and too little on the actual gameplay contents.
Fallout 3 is also a sandbox-style game, very similar to Oblivion (except that it's set in a post-apocalyptic world). In this case it also feels like the developers concentrated way too much on the technology and too little on the contents. The main quest is really, really short. While there are countless sidequests, they are not mandatory nor especially alluring. If you have got immunized to the sandboxing by past games (as I was) and are not very interested in sidequests, and just keep playing the main quest, you will find yourself completing the game in a few days (as I did).
There's nothing inherently wrong with sandbox-style gameplay. It's just that it feels that it often detracts from the actual playing. Ironically, too much freedom can be detrimental to the playing experience once you are immunized to it.
The problem is that many game companies are infatuated with showing their technological prowess by publishing their own sandbox-style games.
I feel that a solution somewhere between utter linearity and total freedom could perhaps be better. Many Japanese RPGs have much of this: They have some degree of free exploration, but not too much (ie. not so much as to detract from the actual playing, nor at the detriment of the gameplay).
Oblivion was a nice experience, but sadly it doesn't have that marvel anymore.
Update:
I think I have a good idea now why I find sandbox-style games so boring: It's because they give you everything (in this case the entire outworld) right from the start. There is no challenge, nor rewards granted when you overcome those challenges.
It's like if you played a role-playing game, and you started with all your stats maxed up, and all the best weapons, armor and accessories in the game. That might be nice for a few hours, but it gets quickly boring: There's no challenge in actually getting those stats and items.
Likewise if you got all the weapons and a full inventory of items in a first-person shooter right from the start: Nice for a while, but gets boring pretty quickly. Again, there's no challenge, and there are no rewards for advancing in the game.
With sandbox-style games (as opposed to somewhat similarly styled JRPG games) it's the same: You get the whole outworld right from the start. That's it. You're welcome. There's no challenge in actually "unlocking" the outworld as you advance in the game (like is very typical in JRPGs and other similar games). There are no "new scenery rewards" for completing quests and tasks. You don't get to go to a completely new and unknown place/city/town after completing a difficult quest, because everything is open right from the start.
As this is the case, the only actual challenging gameplay left is completing the tasks/quests for other reasons, and in this case, as I commented earlier, the outworld is actually somewhat getting in your way because of being so big and basically bereft of any story-telling.