First time I've ever heard this claim about horse naysayers. Do you have citations?

Interesting off-topic: according to Vaclav Smil, the number of horses in the USA peaked in the 1930s. In Europe, later still. David Edgerton's book The Shock of the Old talks about horses as well, among other "outdated" technologies.

People thought fossil fuels were a finite resource back then?

I mean, I wouldn't be surprised if someone thought that, but given the frequency with which oil was being discovered, it seems reasonable that people would have assumed it to be effectively unlimited.

Even in the late 1800s when cars were just starting to be used, the ultimate scarcity of fossil fuels (including coal) was explored by Jules Verne who suggested hydrogen as a successor fuel in The Mysterious Island. And local scarcity of fossil fuels was acknowledged since everyone knew that oil wells started reducing output after a few years.

Nikola Tesla spoke glowingly about how we don’t need coal, oil, or gas if we just harness the energy around us (what he meant here was quackery, unfortunately, but wind and solar accomplish very much the same thing). People understood from the beginning that coal, oil, and gas are finite.

IIRC, people did think we were going to run out of coal back then. A minority, but yes, I do recall some quotes from the 1800s about the exponential growth of coal usage and that people were using too much coal.

But by the time ICE engines were getting invented, it was a done debate IIRC. Horses used to pull trains after all, the steam engine replaced horses in train-usage decades earlier (https://en.wikipedia.org/wiki/Wagonway, for the animal-based predecessor to trains)