One of the ways to do it was to eliminate as many annoying or unfair factors as possible. Something like an extensive macro-management of your empire, where you build your town; you develop it, colonize or conquer another place and then do it all over again, and again, and again. And after you do it twenty times, it's not fun anymore, but you have to keep growing as otherwise you would be destroyed by the guys who have more towns, villages, and castles than you and the game starts taking more and more time, giving you less and less entertainment. So, after a bit of a pondering about how to fix it, it was decided – one player can have only one town.
This decision presented a few new challenges to solve, but at the end I decided to split the whole area into cells with the size of 5 x 5 fields and each cell to be a domain for one player. All cells would contain the same set of map objects, but located randomly (as well as player's towns) to create a general picture of a random map, which would give at the same time the same opportunities for all players.