I'm unoriginally in for the Negotiator as well, but it was close for me between that and the Soldier. Any character I'm likely to play for my own enjoyment likely has levels in one or the other -- the Negotiator for pretty much every one of his class abilities, and the Soldier for good hit points, decent attack and defense, and the power to put somebody on the ground hard and fast.
Surprised to see so little love for the Soldier here. He ain't flashy, but come on -- look at the damage! You need somebody to put something on the ground, that's the Soldier, plain and simple. An old campaign's loose-cannon police officer, a Fast4/Soldier2, was pretty much my fight-breaker. I'd lovingly craft bad guys to ambush the party in the dark warehouse, and he'd turn, Double-Tap with his Desert Eagle, and down would go the bad guys.