One of the big problems with champions in the numbers are so variable. If I start in an area and have one poor quality champion I can recruit, things may be a bit difficult to start with, Alternatively if I have 5 I can recruit from the get-go, I'm going to have a fairly easy time of things in the beginning, and an even easier time later on.
So the following could be enacted to counter these concerns. Two changes:
1. Change champions so they are NOT NPCs standing around the area to be attacked. Instead there are a limited number of Champion-Huts that exist. Entering them with a Sovereign or Champion gives the option of recruiting a truly exceptional champion. These guys are pretty impressive, but to even recruit them requires researching into the recruitment tree.
2. Add a side-branch to the champion recruitment/quest enabling research tree. This tree activates a champion-slot. You begin with a single champion slot, and can gain more through research, up to a maximum (that can be breached through high level repeatable research, but a baseline number of slots are available through the normal research tree). Upon gaining a champion slot a number of random champions are offered to you in the same way as leveling up a character or city offers a random selection of advances. Most champions are common rarity, but some exceptional champions are uncommon or rare.
The effect of these changes are two-fold. It reduces the number of champions to a managable level by linking it to a measurable advancement, the research tree. Instead of being an action with low cost and minimum speed (some gold = instant powerful warrior), it requires investment in research to gain more than a couple of champions. The randomness of the champions is preserved by being a 'choose through a window' option, as well as some exceptional champions being available through champion huts, but even these world-based champions require some investment and can't just be picked up for a few bob and a pickled egg.
As well as that, it reduces the problems of having someone start surrounded by the opposite faction's champions. Champion huts are for both factions, and can be used by either side while offering faction-appropriate champions.
This opens up other civilisation/sovereign creation possibilities. Perhaps the Warlord Sovereign starts with a bonus champion-slot rather than gaining XP from his champions, or a civilisation can start with a bonus to the level of recruited champions.