Consider this. Before Captains were introduced, I and many other players I knew roleplayed captains amongst our troops already. Does this make the introduction of them as a game mechanic not a good idea?
But captains have a game mechanic purpose other than just giving extra strength. They incite characters to safeguard their unit to keep the good captain they have; they reduce unrealistic suicidal charges.
For those players who like to cut down on travel time - and get small advantages to leadership akin to characters holding certain Items - horses could be a nice thing to have too.
But Carts already exist to cut down travel times, and I don't see how you should get a leadership advantage.
I'm not saying I am against horses as flavor, I wouldn't really mind. I just don't see what they bring exactly.
