What would you do in this situation? [3.5]

[Telonius]

Forge a prophecy. "(vague description of your current party) shall lead Hillsfar into a glorious new age." Or some similar blather. At level 25, it shouldn't be too hard for you to get the townsfolk to believe it. Let it spread a bit, and wait for a few peasants to start to realize it's about you guys. Then go to the current king/dictator/whatever, and tell him that you're aware of the prophecy. The peasants are getting restless, and you'd love to make sure that there's no disorder in the land. They're going to believe it no matter what happens now. Offer to work with him to manage the crisis.

"And ruling that whole country was quite a lot of work, wasn't it? You've made a lot of enemies along the way. With us in charge, the target will be off of you. You can retire in style, with a guarantee of safety and more riches than you could ever dream of. You can even keep your title if you want, or we can invent some new kind of honorific for you. History will remember you not only as a great conqueror, but the ruler wise enough to see the will of the gods."

Of course the unspoken threat would be that you won't be as agreeable if he resists. And having that conversation will win you some serious brownie points with the local population. If he refuses (and he probably will) you have a plausible justification when you execute him after the overthrow.