If you're reading this, then like me, you probably had the same headache dealing with multiple cities unrest penalty on a huge map.
I enjoy this game, and I'm a little obsessed with expanding my territory. So this is how I deal with unrest penalty in my games. It's been working out great so far. I now capture every city I see, build new cities when I find good lands, and I don't have to worry about unrest penalty too much.
This is how it works.
Henchmen:
If you play the Altairan race, or customize your own with the Altarian blood, then your Kingdom/Empire will gain the ability to acquire henchmen somewhere down the line in the Magic Technology Tree. These are like weaker version of champion heores, except **You** can decide what class you get. To me, I spend all my fames on training Commander classed henchmen instead of waiting around for random hero to spawn.
Here're some tips get some quick freebie levels for your newly trained units:
1) Fortress gives all trained unit +1 Level
2) Don't use the default henchmen, design your own! Make sure you click the Henchman tab in the creation interface so you are creating a henchman unit instead of a regular unit. Then go to the Trait section at the last page and pick the +1 Unit Level Option.
3) This is optional, but still useful. If you play our own created race, you can pick the "Warrior Caste" trait that will give all your trained unit +1 Level.
If you have at least two of the above, then as soon as your henchman is completed he can immediately pick Administrator I and II from the Commander Tree! That's -10% from Administrator I, -15% from Administrator II, and the Commander class itself also gives a default -15% unrest to stationed city for a total of -40% unrest... per Henchman!
Naturally, you're going to need a lot of fame since each henchman will cost you 20 fame to train. Other than completing Quests, your major source of fame will be from building Almhouses (Level 3 or 4 city, I can't remember off the top of my head).
Have fun! And enjoy taking over the world!