I found this cool (German) map on Wikipedia. I think it could make a good map with about 200/300 territories. Territories would be the cities (+surrounding country), bonuses regions of empires and superbonuses for the empires. And possibly a few tribes (Gepiden, Longobarden etc.) around the edges of empires that are not part of any superbonus.