Grand Theft Auto IV
Since GTAIII, what has made this series work so well is the depth of detail, partly in graphics but primarily in the robustness and variability of the game world. Characters are fully implemented, and missions vary widely.
The game world is further fleshed out by numerous concurrent and optional missions, so there is always a sense of player choice or determination, even though the main campaign is mostly linear and determined. In short, a lot of production has gone into top-level design, and it pays off big time.
There are a large number of situations which do not respond logically, but the player happily forgives this because the implementation is already so detailed. Players greatly appreciate the amount of work that goes into making a robust game world, and the depth and breadth more than makes up for the periodic lapses, the seams and traces of artificiality.
The major structure is equivalent to standard RPG: main-line campaign missions plus optional missions. This is an extremely common and an excellent format for sandbox gameplay: one central campaign (itself perhaps multi-threaded), plus a large number of side-missions. The sandbox all by itself is strong, although making your own fun can get boring after a little while. But crucially, the writing is thoroughgoing, so in addition to base sandbox play, there's always a choice between things to do.
Sandbox play is essentially amoral/non-moral, in the sense that real action is often governed by the hypothetical: "What happens if I run this guy over?" -- this is not a malicious thought; on the contrary, it is quite playful. But this generates a problem: how should the game respond? The GTA solution is to mock realistic response without actually enforcing it, and characterize the PC as logically as narrative ingenuity is capable of.
Grand Theft Auto IV
Still, until GTAIV, the PC personality was something of a narrative problem; as others have written, the hero was a bi-polar thug for whom nothing was truly out of character. Such a character is not terribly interesting: this is facile characterization from the perspective of the writing, and it's not particularly compelling in the sense that we can't relate to the character.
With GTAIV, however, the PC is framed very carefully, and the scarred warrior turned ironical and embittered anarchist justifies much better the peculiar range of action of a GTA hero. This goes to show how well a carefully worked out narrative can match the gameplay.
The problem of NPC response is the simple problem of AI. In the absence of strong AI, all the responses have to be hand-written, which means there are going to be some edge cases no matter how thoroughgoing the design. As suggested above, certain lines -- though they may be realistic or logical -- are nevertheless problematic and counter-productive, and best to ignore even if this does create a seam.
In any case, NPCs reactions always follow certain lines, and practically speaking, they cannot be extremely finely tuned to player behavior. They will fail to respond or respond incorrectly if the player's behavior does not fall into predefined categories. That is, quite simply, unavoidable.
It's a problem, but on a case-by-case basis it can be finessed by clever writing and design. For example, at the beginning of GTA IV, the "first drive" is bound to be messy, of course: the player is still learning the controls. In addition, the player needs to be eased into the peculiarities of believable world minus consequences, and NPCs who seem real, but who are strangely tolerant of behavior that would be taken as extreme in the real world. We need an NPC to guide the player, as part of the intro-tutorial, but how is the NPC going to respond if the player crashes the car?
In this case the writing supplies the solution: the NPC is extremely intoxicated, so he doesn't really notice (or doesn't really care) that the vehicle is getting trashed. The NPC is there to say lightly-disguised tutorial-oriented instruction, and to introduce the player to a world without consequences -- all under cover of the intoxication conceit.
This kind of case-by-case problem solving is the stuff of strong design. GTA's implicit recommendation is that the game be designed very carefully and strategically, with such problems well in mind, so as to avoid as many problems as possible.
Beyond that, where characters are concerned, it is probably best to treat the remaining problems by brute force: if there are ten edge cases in this scenario, script responses for all ten. Solving the general AI problem sufficiently is so far off that it's not even worth thinking about. Even the efforts of avant-garde artists (such as http://www.interactivestory.net/) all demonstrate that the bottleneck is case-handling and writing. In short, the bottleneck for apparently-intelligent behavior is writing for each case.
In direct opposition to the notion implied by the metaphor, sandbox design requires more top-level design, not less. To be frank: the great risk of the sandbox is that it can be boring.
Where the sandbox is the main part of the game, sometimes the game is impossible to "master": instead you can just juke around with it until it grows tiresome. In this case, there's no artfully-crafted narrative, so no climax; there's no reward scheme or gameplay-building (such as technique-training and gradation of difficulty). All told, it is weak on conventional game-design fundamentals. The added freedom makes up for this to an extent, but the problems must still be addressed and overcome by the gameplay design itself.
The space-empire-building game X3 is a solid example of this. There is a main campaign, but it is secondary to the sandbox play. (It wasn't carefully designed or written, which is unfortunate, but let's leave that aside.) The game shines as a sandbox involving the handling of complex systems, and the emergent behaviors are interesting, on a systemic scale.
In the end, however, managing the empire becomes something like a full-time job, the goal and reward being that you have a stranglehold on a single-player universe. From one perspective, it's fun to gradually corner and master a dynamic system, but from another perspective it's -- well, let's just say that one might be inspired to existential or self-ironical thoughts: "why am I doing this?"
Where there is a narrative alongside the sandbox play, one of the main problems is the pacing of the narrative. Do we allow free play simultaneous with the progression of the story? If not, how and with what justification do we interrupt the story in order to allow periods of free play? And then, how do we avoid the scenario where a lengthy round of free-play strains the pacing of the story?
As always, the particular solution will depend on the situation, on the game's unique features and format. But to take an example, another space game, Freelancer (2003), handles this exceptionally well. Gameplay is divided into discrete chapters, and as naturally as time passes between events there are periods of free play; the writing very carefully makes natural these breaks in the action.
One way the writer answered the problem of pacing: the non-player characters are always impatient with the player character. So no matter how long the player took, the response is logical. More critically, when the climax comes up, and pacing becomes particularly important, there are no "freelancing" episodes between the missions. This preserves narrative integrity, but the sandbox "free play" quality of the game is bracketed during this sensitive section. It goes to show that story and sandbox are sometimes very much competing principles.
Freelancer is especially worth mentioning because after the story finishes, the game becomes boring very quickly. There are only a few randomly-generated missions, and by the end of the game, the player has probably already played all of them. There may or may not be new places to explore (depending on how extensively the player freelanced during the main campaign), but there's nothing truly new.
The point here is that there's something cathartic about seeing the credits roll. Gradually losing interest as the game becomes more and more obviously repetitive -- this is an ending with a wimper. But on the other hand, there's always mods (and if you're technically inclined, there's always modding, which can be even more fun). And of course, there's always multiplayer.
The future is bright. The sandbox lives on in perpetuity. And life is good.