I'm okay with quests opening champions rather than a simple gold cost
Champions should be charismatic heroes joining your cause for a reason they believes in (money could be one of them) - not mercenaries you hire paying them once and then endure whatever you make them do for the rest of their lives just to get better equipment I guess 
... or are they slaves you buy from the owners of the locations you find them in?
Give the champions a loyalty stat and some personality traits that will make them leave you if your actions/special event/conditions don't please them. For example you get other champions they can't stand around for some reason, not completing their quests in time (the one you got him with and other ones they throw at you at level up or on special events/conditions of your sovereign/faction/enemies)
There is one possible problem I see resulting from this - One player can scoop up all the heroes on the map, not to mention with the number of heroes present of either faction you would quickly bloat your army.
That will not be a problem if you had to:
1. Research questing to get access to difficult quest that grant high level champions
2. Find quest locations, starting and subsequent ones (increase the count and distance to them according to the lvl of the champion you gonna get) - and btw stop showing where the quest locations are even tearing the fog of war - it kills the exploration part 
just mark any unvisited location with some marker/tool tip hint
3. Complete the quest (maybe even with the help of the champion you will get as reward that joined you on the previous location, but will leave you if you don't find/complete the last one - loyalty stat can prevent you from stripping him of his belongings)
4. Keep all your champions happy/get rid of the ones causing too much trouble
the quest should indicate if you are hunting a hero to assassinate or recruit, to keep the faction specific heroes relevant. It would also solve the issue of opposing heroes being far too easy to kill.
Killing champions aligned with enemy factions standing around waiting to be hired just to prevent enemies to hire them or as an easy lonely target feels really cheap I always thought that the only way you should encounter a champion you'd want to kill is leading an enemy fraction army. But now that you mention it finishing the quest, but not in a way that particular champion wanted so he attacks you instead of joining in or having a chance that a champion you pissed off long enoug becomes a traitor and convinces half of the units of the army he is in to rebel against you and align with another faction or go bandits and starts fighting the remaining half of that army sounds really cool 
