I don't think Soldier of Fortune's violence was really that different from FO3. It did look more nasty, but it was still kind of dumb that you could shoot a guy's both legs off with a 9mm pistol. It just came off as cartoony and juvenile. The sequel did a more convincing job all around.
One game that managed to portray violence in a pretty stark and effective way was Operation Flashpoint. When you're lying behind a bush as bullets fly over you, and you turn your head and see a dead squad mate whose face has been replaced with gory mess so that his facial features are completely unrecognizable, it's definitely not hilarious in any way. War is not fun, and the game manages to get its message across through visuals like that instead of having to resort to cheap ways of emotionally engaging the player.
Personally I'd like to see more brutal violence in games. This doesn't necessarily mean more blood and gore, but a more believeable display of the forces at play and a more realistic sense of weight. For example, Severance: Blade of Darkness had really satisfying combat with appropriately used flying heads and limbs. It wouldn't have even needed all that, uh, severance, because the overall feel of the combat was just right. That's what I'd like to see more. If you hit someone in the face with a hammer, he won't fly ten feet backwards and do a backflip, and his head isn't going to explode either. Still, that's what you usually see in games: weightless ragdolls flying around and/or cartoony displays of flying body parts combined with a puff of red smoke. There are some games where this works (the over-the-top ragdolls in Hitman 2 being one example), but often it just looks and feels terrible. It's even worse if hitting someone in the face with a heavy blunt object has no visible effect except a loss of hit points.