From the basic Swords and Sorcery fantasy up through the Weird West/Wild West eras of fantasy, the noble steed is a constant companion. He is not abandoned until Modern, and futuristic settings, and even then the horse finds ways to sneak back into the game. There is a certain mystique to the image of a knight riding astride his destrier with lance lowered, or the man at arms swinging his sword in a killing arc.
So what would you world be like without horses?