You can easily get this feat at 2nd level as a soldier, or 3rd level w/ 2 Pirate and 1 Soldier. A fifth level soldier with this feat and the same 18 Str (for parrying) and Cha (a bit high, but I'll use the same numbers) can have:
10 +4 (Str) +4 (Cha) +1 (Parry Feat) + 4 (Shield) +5 (Expertise) +3 (Base Parry) = 31 defense. Effectively 33 when you work in Steely Gaze.
A corresponding 5th level soldier with 18 STR, weapon focus, and an akbitanian weapon gets +11 to hit -- and needs to roll a 20. This isn't some average opponent either, but a really good one! The difference will roughly stay the same at higher levels, as the fast growth of base attack is offset by stat growth in both Str and Cha.
With a Shield and the parry feat this other soldier's defense will be 22, and he'll be hit on a 16 or better (accounting for use of Expertise).
That's 5 to 1, and it jumps to 9 to 1 if the victem foregoes a shield. Pretty good for a single feat! If both parties have Expertise this is offset somewhat, but even then it's a strong advantage.
On the other hand, if your opponent is dressed in Full Plate wielding a Greatsword, it'll be difficult to get the Finesse attack you need to bypass his armor while using Expertise, and you end up with about the same chance of finessing the plate mail as you have of getting hit by the Greatsword through Medium Armor if you don't use Expertise, which seems about even.
I suppose in the end I'm convinced it's not broken, just really good. The saving grace is that Heavy Armor and Two Handed Weapons are innately so devestating in Conan, plus it takes a feat and good stats. Still, your opponent better have Full Plate and Sense Motive. ;-)