1. Minor factions leaders - leaderless faction spawns will follow them e.g. if "Robin Hood's" party appear, nearby Forest Bandits parties start follow his party and Mountain Bandits parties will follow "Jánošík". Every of faction leaders has own banner, (often in bad quality, when we're talking about Outlaws). There are few leaders in every factions. Most of them could be taken captive and released (for gold or faction relation boost) or executed.
2. More mercenaries (Amazon, Nord Corsair, Sarranid Nomad, Adventurer, Dwarven Adventurer, Drow Pariah, Paladin Outcast, Witchhunter, Orcish Bravo) and faction elite troops - Ridas Magocracy have 4 types of elite troops

And if we talk about mercenaries - they should be neutral to undead troops in party.
3. Unique spawns - often lead large army, have unique household troop(s) and historical background ( and pretty cool banner too

) - I will add some unique spawns propositions in the evening.
4. Vedmak could have two swords (second as shield of course) instead shield.
Edit:
Unique spawns:
Faction: Outlaws
Sir Kiril the White
Background: Nobody knows from where the young knight named Kiril came. Once he was a Grand Inquisitor of Blazing Hand and has practical rule over Order. When he took this position the world learned about his fanatical nature. He was merciless to magicians and even for people who have something in common with them - he was burning people at the stake for just talking with someone suspected of witchcraft. In madness he even had the plan to start the war with "heretic" Vaegirs Kingdom and was sending his Witchunters on their lands. Some say that he drank the blood and devoured bodies of his victims and he must be demon or vampire, but fanatics claim him to be savior of the rotting world. Terror lasted until the Grand Inquisitor accuse Grandmaster of heresy and attempted to burn the Blazing Hand Temple. The siege lasted several days until the army of Vaegirs arrived - Kiril's bands were roaming their countryside and burns villages. King Yaroglek didn't wait with response. The Inquisitor's army was slain and he was placed on the process, but one day he just disappeared from guarded prison cell. Knights believed that he was in possession of demon and dark powers help him with escape. After bloody reign of Kiril, the Order changed. Grandmaster introduced many reforms, inter alia: limited power of Grand Inquisitor, introduced tolerance for magicians, made order more secular and less fanatical.
Character description:
Race: Human (in fact possessed by demon)
Hair: long white
Beard/Moustache: no
Eyes: entirely white
Face: young and handsome
Character: evil, but he talks like paladin
Class: Dark Cleric
Skills: around 80 strenght (because he is demon and must be very powerful), max in ironflesh, faith and strike, high proficiency in melee weapons, immute to magic
Equipment: silver Blazing Hand knight armor without helmet, Purificator - flaming two-handed sword
Banner: Blazing Hand banner with red fist and flames instead of blue
Party:
Dark Inquisitors - unique elite troop, human race, dark cleric class, immune to magic, wear hooded black armor, using mace + shield and axe + shield, possessed by demon so really strong one
Witchhunters - appears as mercenary in taverns too, so it's not unique for Kiril, using crossbow, and some blunt/sword weapons + shield, wearing leather armor, have good resistance to magic
Fanatics - weak monk-type unit
Party consists of:
20-30 Dark Inquisitors
100-150 Witchhunters
400-500 Fanatics
so it's really big challenge.
Options when get him prisoner: execute him ( boost relations with Blazing Hand & Vaegirs - he turns into dust as well as his powerfull sword), let him go for ransom (huge amount of denars), let him go for sword (only once, his sword has levels of power - when you get it it's weak and not flaming but when you kill certain number of living creatures it will upgrade [you will lose worse version and get better; demons count as 2 or 3 killed units ] ), just let him go (get relations with Demons).
Unlike the other unique spawn's, when killed he will also return. When Demons arrive he will come back and be added to their vassals as Kiril the Black - with same skills, but with twilight armor and other flaming sword, with giant shadow race ("golem") and reversed banner of Blazing Hand - red fist/flame, black background.
His army will be as big as other Demon lords (not as big as when he was unique spawn), it consists of Dark Inquisitors as elite household troop, medium and low tier demons.
Edit2:
Vizier Arif (aka Jackal)
Faction: Outlaws
Background: Sultan Ayzar's younger brother. When he was just a boy, he was sent to Ridas Magocracy to learn about all kinds of knowledge. So when he returned after many years, he was prepared to take the position of vizier at his brother court. Arif was widely respected and his advices led to the flowering of Sarranid Sultanate. He was ambitious but loyal - after the death of his brother he served on the court of Arwa and her husband. After Baybak death, Hakim knows that Arif remained loyal to Arwa and wisely considered him as great danger. He accused him of killing both Sultans with help of black magic, using necromancy (though it's not banned in Sarraind Sultanate) and for treason as he did not consider him to be the new sultan . Arif was exiled and he fled to far kingdoms behind the sea. But now he returned to Calradia and he is seeking for vengeance.
Character description:
Race: Human
Hair: cropped black
Beard/Moustache: cropped black beard
Eyes: brown
Face: not really old (he is old but he is mage too) and long
Character: upstanding
Class: Necrowarrior
Skills: good necromancy and warrior skills, high magic skills too
Equipment: decorated sarranid armor with helmet, royal sarranid scimitar, sarranid horse, magic
Banner: black jackal on yellow background
Party:
Champion of Jackal - unique, [elite] better version of Rider of Jackal, mummy race, very resistant just "mountain-that-rides"
Rider of Jackal - unique, better version of mamluke, using twin scimitars instead blunt weapons and shield, human race, higher riding and athletics (cannot upgrade to Champion)
Sarranid Horseman
Party consists of:
around 5 Champions, around 30 Riders, around 70 horsemen - it's not huge, but very mobile and elite army.
Options when get him prisoner: execute him ( boost relations with Sarranids and Hakim, lose relations with Arwa the Pearled One), let him go for ransom (huge amount of denars), let him go for nothing (boost relations with Arwa, lose with Hakim)
also you could persuade him to join your cause (only when Arwa is in your party) - he will challenge you to fight 3 of his Champions and after that Arif himself (magic is not allowed), when You win, he will join Sarranid pretendent cause and you get positive relations with some of the Sarranid lords . If you lose he also join your cause but you will lose renown and relations with him.