The Sea Protected and Nurtured Horses
(I realize this is a 5 year old question, but it was so interesting I had to look into it.)
Probably, Poseidon was linked to horses because the Sea was seen as protecting and nurturing horses. This belief would be truly ancient, pre-dating Mycenaean Greek culture by nearly two millennia.
Vedic Connection
Since Greek Mythology is a daughter of PIE Mythology, (and the ancient Greeks themselves had significant Steppe Ancestry) the first question is: do other Indo-European cultures link horses and the Sea?
And the answer there is a resounding: Yes!
WHAT time, first springing into life, thou neighedst, proceeding from the sea or upper waters,
Limbs of the deer hadst thou, and eagle pinions. O Steed, thy birth is nigh and must be lauded.
Rig Veda CLXIII (emphasis mine)
To him let us address the song well-fashioned, forth from the heart. Shall he not understand it'
The friendly Son of Waters by the greatness of Godhead hath produced all things existing. [...]
Here was the horse's birth
Rig Veda XXXV (emphasis mine)
These two verses from the Rig Veda - the first in praise of the horse itself, and the second in praise of Agni, known as the Son of Waters - both state the the horse comes from the Waters, or that the Waters were responsible for the horses birth.
If there is a strong linkage between Horses and the Sea in both Rig Vedic culture and ancient Greek culture, the mostly likely explaination is that both cultures inherited it from their common ancestor, the PIE culture.
Why Does the Sea Protect and Nurture?
Which brings us to the question of why the PIE people associated the horse and the sea. In The Horse, the Wheel, and Language David Anthony describes how the steppe economy would force Yamnaya / PIE herders to winter in the marshlands where major rivers emptied into the Black Sea, Caspian Sea, and Aral Sea, since the steppe was too cold and dry to support their herds during the harshest months of the year.
Since horses preferentially foal in the spring, PIE people would have spent all winter near the Sea, and the major rivers (Dnieper, Don, Volga, etc.) watching their mares become more and more visibly pregnant.
Then in the spring they would go out into the steppe and foal.
It would have been natural, then, to see the horse as "proceeding from the Waters" - since the Sea and the Rivers seemed to have protected and nurtured the mares and their foals through the hard, cold winter months.