Obsidian Entertainment producer/designer Nathaniel Chapman tackles difficulty settings and how they affect a game's challenge in his very first blog entry over at the company's official website. Read on:
...in my opinion games tend to offer the most interesting difficulty options when they rely on tweaking or even adding new core challenges without invalidating the core gameplay. A great example of this is Thief. Thief's difficulty options added new challenges to their already existing stealth gameplay. They didn't choose to increase enemy health (at least, as far as I remember) because that runs at cross purposes to their core stealth gameplay. Instead, they force you to not kill anyone. This makes the game's environment navigation and perception/awareness challenges much more complex, but doesn't really alter the core balance of the weapons and tools.
The reason why more blunt instruments, like just increasing health and damage, tend to fail IMO is that they don't actually make the game more challenging, they just mess up the pacing. I played an ARPG recently that scaled damage and enemy HP and rather than really being more challenging at higher difficulty levels, it just turned into a massive slog. That's something you really want to avoid at all costs... pacing is key to the game being fun, and hard doesn't mean frustrating or boring, it should mean challenging.
So for instance, if I were designing difficulties for GTA I would probably make the guns more differentiated and single purpose in harder difficulties (IE less general purpose, innacurate guns become more inaccurate, short range guns become more short range, etc.). I might make ammo more scarce, though that can risk hurting your pacing. I might even change the handling profiles of some of the cars to make them more swervy, and a little easier to lose control of. What I wouldn't do is reduce your car's HP or increase enemy HP. I feel like those changes would just make the game more frustrating/dull, not harder.