The earliest instance of this expression that I have been able to find is from John Ray, A Collection of English Proverbs (1678), which has this entry (without further comment):
He is so hungry, he could eat a horse behind the saddle.
Unfortunately, neither Ray nor any other author who cites or uses the expression offers any explanation of why it focuses on horses rather than some other animal.
Tobias Smollett, The Life and Adventures of Sir Launcelot Greaves (1760) is one of the earliest recorded instances of the expression used in a narrative—in a scene in which Sir Launcelot has delivered a squire from the curative regimen of an incompetent doctor, nurse, and apothecary, and has asked the patient how he now feels:
'I should feel heart-whole if so be as yow would throw the noorse a'ter the bottle [of medicine, which were thrown out the window], and the 'pothecary a'ter the noorse; and oorder me a pound of chops for my dinner; for I bee so hoongry, I could eat a horse behind the saddle.'
And likewise from Walter Scott, Guy Mannering; or, The Gipsey's Prophecy (1815):
Gipsey Girl. I'm sure, gentlemen, you'll excuse us; we are not accustom'd to see the like of you; but if there is any thing that you would take—
Dinmont. Can there be anything we won't take, my dear? For I have not taken meat or drink this four or five hours, and the cold blast on the hills has given me such an appetite, that, as the Yorkshire-man says, "I cou'd eat a horse behind the saddle."
But it seems to me that some readers may be misreading the sense of "a horse behind the saddle." The suggestion I have read elsewhere on this page is the "behind the saddle" means "posterior to the saddle," which is to so say "toward or at the horse's buttocks." But I think it is just as likely to mean "through the saddle."
Horsemeat has, deservedly or not, a reputation for being stringy and tough. In countries where horses are not a meat source of choice, the bad reputation probably rests of several factors: horsemeat has a stronger flavor than beef (for example), it is (or was) commonly used in such countries as meat for dogs, and because horses are generally bred as riding or pulling animals and not as sources of meat, their meat tends to be far leaner and less tender than cattle bred and fattened up for slaughter.
In a culture where horses were far from the preferred meat source, people may have eaten them only in straitened circumstances, when no other source of meat was available, such as in severe dearths, with consequent privation for the horse prior to its being eaten, too—and again this would tend to reinforce the perception that their meat was inherently tough and stringy.
In any case, the fancied (and under some circumstances real) toughness of horsemeat may be the point of the expression. A person who is ravenously hungry may express this fact by asserting not merely that he (or she) is hungry enough to eat a horse, but that he (or she) is willing to go through the saddle to get to it.
English dislike of the idea of eating horsemeat seems to have been quite strong in past centuries. For example, in Home George, Memoirs of an Aristocrat and Reminiscences of the Emperor Napoleon (1837), we have this remembrance of the eating of a dog aboard an English navy ship in 1777:
When we were in New Zealand, Neddy Rhio, one of my messmates had got hold of a New Zealand dog, as savage a devil as the savages from whom he got it, and this same dog he intended to bring home to present to the Marchioness of Townsend, his patroness. But one day, while Neddy was on shore on duty, a court-martial was held on the dog, and it was agreed nem. con. that, as the dog was of cannibal origin, and was completely a cannibal itself, having bit every one of use, and shewn every inclination to eat us alive if it could, that he should be doomed to death, and eat in his turn, we being short of fresh provisions at the time. The sentence was immediately executed, the dog cooked, dressed, and eat, for we could have eat a horse behind the saddle, we were all so confoundedly hungry; ...
It seems odd to justify eating a dog by saying, in effect, "of course we ate it; we were so hungry that we'd have been willing to eat a horse." Another instance of anti-horsemeat sentiment occurs in "Paris Sport and Paris Life," in Baily's Magazine of Sports and Pastimes (March 1865):
We have all heard often enough, especially on seasons like the present one (confound it!), of horses 'eating their heads of[f].' Well these experimentalists [in Paris] want to save them the trouble, and propose eating not only the heads, but the legs and body also.
This Hippic Society, which should be called 'The Eat-a-horse behind the Saddle Company (Limited),' actually had a dinner last week at the Grand Hôtel. Nothing but horse was served! The menu, as far as I can remember was as follows:—
Potage a la Reine. Cotelettes de Hock. Saucce aux Eperons. Legs of Screws served in their boots, Potted Favourite—a 'good thing' boiled over (This was not much relished.) And lastly, a saddle of horse garnished with girths.
The company agreed that, except in some of the low-priced Paris restaurants, they had never tasted such meat, and they did not separate till a late hour.
Th 'Charivari' [Puck] had a splendid picture of a pair of carriage-horses shying at the entrance to this horse-eating hotel, and a dog, evidently thinking he was being defrauded of his rights, barking at one of the guests returning from his equine banquet.
I may be old fashioned, but I confess I would rather have a saddle of five-year old Welsh mutton—not too much done—and a few French beans, than a haunch of either of Mr. Henry Chaplin's recent purchases.
This source expressly treats horsemeat as properly being a meat fed to dogs, which again emphasizes its lack of appeal to the (English) writer.