I've always RPed my characters as being on horse. Walking is for peasants.
They would decrease travel times, but only if the player has no unit (army units travel slower than a lone horseman);
You already travel slower if you have a large unit.
they could require food or grazing time, be of a variety of different breeds (mostly just description/flavor differences), etc.
Meh, I'm not sure I want to spend hours grazing my horse every day. That's not extremely interesting gameplay.
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.
Infiltrators aren't ninjas. My infil regularly leads large units in battles. I can't check right now, but I think nothing forbids them from leading cavalry.
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.
That could be nice as flavor, but it mostly duplicates the captain mechanics.
