It might not be a glamorous answer, but it sounds like your ideal elven "horse" is just a standard mule.