Take a look at the non-d20 Song of Ice and Fire game. The rules are totally different, but they can give ideas. I have a FATE DM who was also really good at this kind of stuff.
I played about three sessions of it. The DM gave up on it because the combat rules were ... weird. That's not an issue here. At least you'll be familiar with them.
All the PCs were sworn to the same house. That immediately solved problems like PCs having completely different goals.
Much like social skills in D&D, expect different PCs to step back from any "skill checks". We had a general who was frankly our greatest warrior but not all that bright. Needless to say, he stayed away from any and all intrigue checks, but participated in tactical discussions (in a metagame sense). Expect that. My own PC was the spymaster. He could fool people (actually, he was crazy good at it) but had no real fighting ability and couldn't lead troops either. (He had the equivalent of low Charisma but loads of Bluff. The end result was he only had one real social skill, but he was damn good at it. He was like a slightly less competent, slightly sneakier Littlefinger.)
How good? One time, our lands were infested with a particular band of pirates. (We rolled very low on law and order.) My PC put on a disguise (that was his other crazy skill) and infiltrated the band, using the excuse that he was a con artist pretending to be a merchant... He was nearly killed by the paranoid bandit leader, personally. (The bandit leader had good combat and leadership skills, but wasn't so good at intrigue.) I survived by scaring him with ghost stories.
Which brought up the next part of my plan. I had taken control of a small band of spies, and had them pretend to be ghosts. This was because said bandit leader had killed a priest and so I had something to work with there. Also because pretending to be a ghost was part of my character's forte, much to the DM's annoyance.
The bandits freaked out. Some of them sneaked out, while I had off-handedly mentioned to the bandit leader about knowing a priest. I made sure to talk him into admitting he'd killed that other priest in front of some of his men. Then I riled up the men, convincing them that only the leader's death would placate the ghosts. They killed him, the ghosts miraculously stopped the haunting, and that's how my PC talked someone to death
But note the downside. Other than pretending to be ghosts, the other PCs had nothing to do there. Alas, "don't split the party" is a rule that very quickly falls apart in a political campaign. I don't have good suggestions on how to avoid it, but you should be forewarned.