Try the following:

1. create an soverign and focus on a good combat rating (high hp, attack + defense, take best equip)

2. Attack the other soverign´s asap, dont build a town, just kill em, the faster you kill someone the stronger you get. collect all equipment stashes on your way and recruit all npc if they have some combat rating

3. Repeat till you win

I just finished my 4. game using this tactic, i won all 4 games in under 40 turns (small, small, normal, normal) map. The Towns need some sort of defense, mabye placeable archery towers or some other stuff. Or how about a mage tower that powers up the soverign big time if he is in the town, so stronger soverigns cant just steamroll everything.

Currently its like absoluty no challenge, i have a CR of 8-9 at gamestart and the other soverigns 0-6. After i kill the first 2-3 soverigns i usualy have a party CR of 13-20.