But the question here is how far the horse can go on a single load of food. We're purely trying to convert food into work via the horse.

And if you assume that the conversion of potential energy stored in the food to actual energy produced by the horse is less than perfectly efficient, then it will always be better to avoid doing work than to try to make up for doing extra work by starting with more food. That would be true even if starting with more food didn't require doing even more extra work to move the extra food.

Improvements in strength aren't helpful to this problem; what you need is higher efficiency.