A robust form of common sense believed to be found in poorly educated but shrewd people.
When faced with the task of coining a new phrase, horses wouldn't seem to be the obvious choice of animal to act as a yardstick for mental discernment. Owls, foxes or dolphins maybe, but not horses. Indeed, the person who coined the term horse feathers (meaning nonsense, stupidity) went the more conventional route in associating horses with a certain lack of refined intellect.
Given the animal's important place in the lives of the people of medieval England, where present-day English was largely formed, it's not surprising that we now have numerous expressions that refer to horses. These usually allude to the hefty, coarse or even vulgar nature of the working hacks of the Middle Ages. This perceived lack of sophistication is apparent in the way that rural language was formed. Any plant that resembled another but was large and coarser would be known as horse-'plant name of choice'. Here are a few examples (and there are many more):
Horse-daisy (country name for the Ox-eye Daisy)
Horse-radish (a large root resembling a radish but with a fiery taste)
Horse-gentian (a.k.a. Feverwort)
Horse-parsley (Alexanders - an outsize parsley-like plant tasting of celery)
Likewise, in general use, adding the prefix 'horse' was considered enough to render any item comic (in the same way that Steve Coogan's 'monkey tennis' is inherently humorous). Examples (and again there are many to choose from) are 'horse-fiddle' (a watchman's ratchet or rattle) and 'horse-billiards' (a form of deck quoits using a large wooden disc).
So why 'horse-sense', which seems to go against the usual pattern? In fact, this expression came about in just the same way. The addition of 'horse' to 'sense' was meant to convey an unsophisticated, country type of sense. What is different is that, although the idea of an equine violin or billiards table is ludicrous, 'country-sense' has value, being a common-sense alternative to the high-falutin' claptrap of what we would now call 'men in suits'.
As to where and when the phrase 'horse-sense' originated, my horse-sense tends to lead me towards the wild west and plain-talking men in cowboy hats. The expression is often attributed to the American writer James Kirke Paulding, who wrote the novel Westward Ho! in 1832:
I'm for Dangerfield, though he hasn't got a white pocket handkerchief, and though he can't play the piane [sic]. He's a man of good strong horse sense.
In 1870 the New York magazine The Nation offered a corroborative view of the expression's origin:
The new phrase - born in the West, we believe - of ‘horse-sense’, which is applied to the intellectual ability of men who exceed others in practical wisdom.
In fact, we need to cross the Atlantic for the origin. 'Horse-sense' was coined nearer to the Devon town of Westward Ho! (incidentally, this is the only place name in the UK that includes an exclamation mark) than to Pauling's wild west. The English romantic novelist Evelyn Malcolm wrote a string of novels in the 19th century, firmly set in Daphne du Maurier West Country bodice-ripping territory. One of these was Forsaken; Love's Battle for Heart, published in The London Story Paper, January 1805, which includes a reference to a horny-handed son of the soil:
Lud, Bill Perkins has horse sense.
Or you may just prefer to recross the pond for this definition of the expression, attributed to W. C. Fields:
Horse sense is the thing a horse has which keeps it from betting on people.