Instead of giving them Bonus Feats or Leadership outright, I tried something a bit different. The intent was that while a Bard was sort of a Rogue/Sorcerer, the Aristocrat would be a Rogue/Fighter; no magic, but plenty of social abilities.
ALIGNMENT: Can't be Chaotic. You ARE the Law, after all. Becoming Chaotic doesn't stop any class abilities from working, but you can't advance in the class again until you return to a valid alignment.
NATURAL LEADER: As the Leadership Feat, except no cohort, and only Aristocrat class level counts towards leadership score. This stacks with the Feat, so a pure Aristocrat with the Leadership Feat has twice as many followers as normal. They get this ability at level 1, but unless you have a really high CHA you won't get any benefit out of it for a few levels.
Optional rule: to make the ability better, say that while the Leadership followers are normally Commoners, Experts, and Warriors, these followers can also be Adepts or Aristocrats without a level penalty. The penalty for PC-class Followers is also reduced by 1, but only for Followers from this ability.
KING'S CHAMPION: The Cohort of an Aristocrat can be higher level than normal. The level of the cohort increases by +1 for each 5 class levels up to 20, even if this takes it above the level of the Aristocrat. So, an Aristocrat can have a cohort of equal level from levels 5-9, +1 level from 10-14, +2 from 15-19, +3 at 20+.
(I actually redesigned the Leadership Feat to use a point system, so the above two abilities are different IMC)
Obviously you need to take the Leadership Feat for this ability to matter.
INSPIRATION: similar to Bardic Music, except weaker, uses Diplomacy, and works on more targets.
CONTACTS: As Bardic Knowledge, except instead of information, you're trying to arrange a meeting with the King, find a merchant selling what you need, find a merchant willing to buy what you're selling, etc.
Optional rule: All Aristocrats come from either Noble or Merchant backgrounds; give a circumstance bonus to the check if it's within your background (+1 to +5, depending on how much of a connection there is already, see examples below), and a corresponding penalty if it's in the opposite background. Some things are borderline and get no penalty.
Examples: Bob the Aristocrat is of Noble birth. He's trying to arrange a meeting with his father, the Duke; since there's a close connection already there, give a +5 circumstance bonus.
He wants to find the black market to unload some goods. This is more of a Merchant background connection, so there's a penalty. Since he's in his hometown, it's only a -1 penalty.
Now, after travelling to another plane, he wants to arrange a meeting with a foreign leader who's never heard of his home. The bonus drops to +1; he's a visiting noble with a nonexistent connection.
Next, he wants to find the black market in THAT town. Since it's an unknown place, and it's not really his sort of thing, it's a -5 penalty.
If you don't want to bother with this, just drop the circumstance modifier, but then you can get some strange situations.
maybe if you use some sort of "first level benifits only at first character level" type rules it would be worth coming up with something... 
