Nobles should be able to purchase and ride horses, in general. They would decrease travel times, but only if the player has no unit (army units travel slower than a lone horseman); they could require food or grazing time, be of a variety of different breeds (mostly just description/flavor differences), etc. Horses might be purchasable by adventurers and priests too. But will cost a pretty penny, mostly beyond the reach of any adventurer. Infiltrators couldn't ride horses since they're not stealthy/blend-in-able. Horses could die if not fed properly, or in combat, and maybe nobles on horseback could gain a small leadership improvement in battle. Horses maybe could have names and descriptions (i.e. Blue, a spotted palfrey) which might be visible in battle or scout reports.
Thoughts?