There are a few ways. If you are a SK or a Paladin their lvl 20 fluff spell is a horse. It isn't very fast, I think it's 20% or thereabouts.
You can buy a horse with guild status points or plain old plat. They cost quite a few status points, so that isn't really an option until 50+. If you go the plat route, the decent horse (40% increase) costs about 9pp and change.
You can quest for a flying carpet in DoF but you need to be high level to do it.