well.... how about " build a Rider academy" as option on your town. when finished, you can recruit 1 rider companion per week.
only companions not troops, so you can level-up 'em , equip 'em, and then, later, you can say " i want you to ride alone" and he leaves the party, joins an empire and goes by his side in the land.