Both the SK and his LTs are just way too easy to kill. Part of that might be because Riders are so amazing, but that's not all.
Lieutenants: Lieutenants are just a curse/graveseal and swarming pikemen away from death.
Can the LTs get more initiative, and some point-defense/anti-swarm abilities that the AI will more readily use? Every time I have fought them, they get off one massive melee attack that kills a soldier pikemen, and then my swarming units murder their asses. They look so menacing wandering the map, but fighting them with a serious army becomes anti-climactic. Why don't they use spells?
One more thing: the Lieutenants wander around the map aimlessly, dancing around my cities not attacking. Can they be confined to wandering a set area, and be more likely to attack my settlements? As they are now, they seem like they have dementia and forgot their mission of 'ruining mankind,' combine this with the ease of killing them and they just don't seem so threatening and interesting.
Killing them is more of an obligation than a fun milestone.
If there could be 1-2 more, so each game had different Lieutenants, that'd also make things more interesting.
In my opinion, the Sorcerer king should be randomly assigned an element each game, and have unreasonable powerful spells that employ that element. Thus coming prepared with elemental defense units/equipment becomes necessary to survive.