"The Leveler was never killed. He was immobilized by sorcery, beheaded and burned at the stake in the Second Era. A thousand years later he was drawn and quartered on the plains before Ileum, the tireless horses dragging the pieces of his lifeless body to the four corners of the world. Again in the Fourth Era his body was destroyed by fire, his ashes mixed with salt and buried under the Mountains of Kor. Balor, Moagim and all those before them wore the Mantle of The Leveler."
Read this, they got horses.
Also in "the Baron" level (the one you sieged the keep), you could see a horse in the narrtor's pic.
Why?? Why there are'nt horses in-game ?
Maybe Bungie tough it was difficult to create a Mounted unit.
But at least they could make it a critter unit, like the pigs.