Stables throughout Thera would offer steeds. They could either be good for a limited amount of time, or a limited distance.

They would increase speed of travel 3 or 4 times, and increase your moves efficiency 3 or 4 times. Some limitations; they are quite expensive, and one cannot be in a group to have one, and cannot follow others or lead others while renting a steed. This prevents massive cavalry gangbangs. Which would be cool as hell to behold, but ouch.

Also, for atmosphere, would leave the occassional dropping on the road which dissolves after a day or so.

They cannot cross water, their efficiency worsens in the mountains.

Different cities might have steeds of different types:
Galadon: Horses; the standard.
Hamsah: Camels; not great for speed, but great for distances, especially in the dessert.
Arkham: Dolphins; only usable in water.
Arial City: arials (taxis) that are limited duration, but cover great distances.

Steeds would consume water/food from your inventory as well.

They crap a lot. Did I mention they should crap a lot?