I think the core problem lies in designing the gameplay loop itself. You start with a sprawling city and fill it with interesting locations. To get to those locations you have to travel, but travelling and just watching your character moving forward for several minutes would be boring, especially if done multiple times in succession. So what do you do? You put in mobs, just to give player something to do to break the monotony. But this has its own implications. If the combat is ruthless and unforgiving, and player is unprepared, he will most likely die and loose some (perhaps a lot) of progress. This can be fun, but it can also quickly turn to frustration.
But let's assume the mob is just about right for the player. Even if you have mobs, i.e. whole groups of enemies, the balance of power should be roughly equal between both sides. This means that the player (i.e. one character, his avatar) should be able to defeat a whole group of NPCs. Which means, of course, that the PC will be so much stronger than any one given NPC in the group. But why, though? Where would his advantage come from, what would make him so much more powerful than a random thug? Better skills? Equipment? Temporary boosts? Everything contributes, but in open world the devs can't predict their configuration, thus problems with balancing. The more variables, the more unpredictable the result, hence balancing issues.
But let's go even further. Let's assume the encountered mob has, say, 5 people. If the encounter is just about right for the player and his current setup, this would mean that:
1 PC >= 5 NPC
But, but, but - there are enemies in the city whom the player cannot yet beat, because they're just so awesome. A thug from another mob encountered earlier one-shotted the player on the spot. This would mean that:
1 thug > 1 PC >= 5 NPC
So the high-level thug is probably several times stronger than the whole low-level mob. And as the game progresses, and as enemies scale - either with the player or because they are deliberately created so in certain areas - the power of characters rises not simply by some arbitrary percentage, but by constant multiplication - to exorbitant levels.
As a way of escaping this level-loop I propose slowing the game down by having combat situations small and far between. Each encounter should be a big deal, something to be almost celebrated, and not an annoying nuisance like those hordes of wolves, drowners or bandits in TW3. Gangs should clearly mark their territories, so that player would know when he's entering dangerous grounds and would have the opportunity to prepare. But when he does, the combat should indeed be tough enough to provide a relatively short yet intense deluge of emotions, something that would be remembered afterwards.
Plus if we don't have throngs of enemies to defeat, we won't be collecting as much loot, breaking the economy in the process.
The question is with what to fill the inevitable times of transition between places. Frankly, I don't really have any ready ideas. My hope is that there will be vehicles in the game, so that transit times will be shorter and chances of random encounters will drop.