Bandits not fun?
How did that happen? Was looking forward to this...
Edit: Issue of original post has been somewhat addressed, so I've changed topic of my post.
I don't think unrest is a huge problem, it gives you a reason to build fortresses with high food. The problem I see is one of pacing. I often get to a place where the area around me has been cleared of quests and monsters, but I don't want to fight a war because I don't want any more cities. I end up not really having anything to do while I wait for my fortresses to level up so I can expand more. Then, by the time I am ready to expand again, it's much easier to go for a quest or spell of making victory. This is especially problematic on the larger map sizes.
Here are a few ideas that might address the issue:
1) More options for reducing unrest. If playing empire or men, I can create "mayors" (sion or henchman commanders) to address the issue, and that helps quite a bit. More options, whether through buildings, tech, or units can give multiple options to allow you to continue expanding.
2) Quest maps for everyone, though more expensive. This might devalue the wanderlust trait too much, but I really like the quest maps because they give you something to do after monster lairs have been cleared, but when going to war isn't a good option. Perhaps instead of quest maps, an item that spawns monster lairs. Not quite as fun, but would serve much the same purpose.
Also, I don't like the idea of a hard cap on number of cities, I think penalizing in much better that outright forbidding. I do really like the idea of a feudal system though, where cities are assigned to a champion, and unrest is based on number of cities assigned to a single champion rather than in the kingdom. This not only adds a bit of story-telling depth, it also allow you control over localization of unrest (if you have a particularly valuable city you could make sure its lord is only assigned to it.) Also, it gives a good reason to want more champions even if you don't have an army available for them to lead.