Currently I'm developing a 4x medieval multiplayer game where I want governments and inner politics to be an important aspect of the game. In my opinion, most games seem to neglect this aspect while it could offer interesting gameplay. To try to create interesting government gameplay I have created a small pool of people that come from the noble houses in the realm. They can be given jobs like general, admiral or governor. The capabilities of the administration are limited so it's important to direct tasks to these people. The next thing I want to implement is loyalty. I want their loyalty to be based on a lot of factors and in a way force the player to keep their vassals' wishes in mind. The other thing I've implemented are sliders with which the governments views on certain matters are set and policies which give a player the possibility to finetune his or her government.
These ideas are a mix of what Europa Universalis and Crusader Kings have to offer but i'm not yet satisfied. If anyone has played a game where interesting choices regarding the government could be made, please let me now. Of course ideas are welcome as well.