I would suggest you read the book "Guns, Germs, and Steel". Its a tough read, but also very interesting.
I personally think that without horses, warfare would be completely different...horses played a huge role in tech development, transportation, and even our immune responses (we developed our immune response to many diseases from our herd animals...which the American Indian did not).

Right off the top of my head, I would say that the most direct correlation to warfare would be no horses means no chariots. Chariots were the superweapon of the ancient world and the basis for the mounted horse archer and eventually the knight...

once again, I suggest reading the book.