As I understand it, I think you'd still see some expansion that parallels early Indo-European movements probably at least across most of the Western+Central steppe zone once the wheel is invented, and wagons and carts become possible, with or without the horse. Those people could be early Indo-European speakers, of a sort, in an ATL (though they need not be).
With David Anthony, I'd doubt that. For two reasons:
a) Without horses, steppe people are probably not buying into the entire herding lifestyle at all. Cattle are dying like flies on snow-covered steppes. Horses are about the only available animal which is suitable as a draft animal and which can eat grass from under an icy snow cover, so they can survive steppe winters. Before (roughly) 5000 BCE, there was almost no group around living in the steppe and doing either herding or agriculture (the Bug-Dniester being the exception to the rule and heavily influenced by Starcevo-Cris). Even afterwards, some steppe dwellers did not switch to herding (Kelteminar, for example).
b) Without the increased complexity and mobility which had built up in the Yamnaya culture at the moment in time when the wheel is ready to be transmitted from Mesopotamia into the steppe, there would probably be so much less contact between the steppe and Mesopotamia in the first place, so the wheel might not become known for a long, long time yet.
It does seem to me like the wheel and the presence of lots of domesticated herding animals, is the pretty decisive factor in this mobility, rather than the horse.
The wheel was important, but Yamnaya emerged before its adaptation on the steppe. Yes, herding in general was an important factor, but, as I said above, I doubt that the steppe is going to take to herding without horses.
We know that at the Botai in Kazakhstan, people seem to have domesticated the horse as their only domesticated animal** - judging by archaeological evidence of milking, corraling, riding - and not have any of wheel or domesticated sheep, goats or cattle. They seem to have lived in villages and permanent settlements, not to be highly mobile and certainly don't seem to have expanded far and wide.
Yes, but the Botai were also the first in their region to herd an animal (horses). The Yamnaya built on way more than a thousand years of herding, from Khvalynsk / Sredni Stog onwards. They had grown numerous much earlier, and the steppe regions where the culture formed had developed greater complexity in contact with Cucuteni-Tripolye and Northern Caucasians. The wheel was certainly important for the vastness of the Yamnaya expansion, but there's more that needs to be taken into account when comparing Yamnaya and Botai cultures.
Likewise, there is some evidence (less strong) that early cultures on the western steppe at Khvalynsk taken to be of pre-proto-Indo Europeans who were experimenting with herding also had domesticated horses. But again they don't seem to have really expanded in the big way that the Yamnaya did (though probably some interactions with cultures in Eastern Europe outside the steppe zone).
Khvalynsk are "ancestors" of the Yamnaya. They paved the ground, metaphorically.
So even if you had a "no horse" wagon based pIE expansion of sorts, it would probably have been weaker in some senses, and maybe less successful in conflicts, and their
language and religion may not have displaced as many others.
Without horses, I bet the wheel gets transmitted to the fisher-gatherer cultures then persisting along the Dnieper, Don, and Volga later than 2500 BCE, probably even after 2000 BCE. The later it is, the better the chance that donkey chariotry has already become a thing in the civilized South. Then, it would still take time to genetically adapt donkeys to the cold steppes. After that, the steppe can catch up - but the civilized South has taken quite a few steps by then.
If the Indo-Europeans expand more slowly, would that mean that the pre-IE peoples could adapt an agricultural package and survive for longer? More Basque-like languages in the west of Europe, for instance?
What do you mean? Europeans before the waves of PIE newcomers from the East certainly had developed agricultural packages, in the South-East from 7000 BCE onwards, on the Middle Danube by 6000 BCE, even in "Germany" by around 5000 BCE, and by 4000 BCE it had reached the Baltic. Being agriculturalists didn't prevent the "Old Europeans" from being Indo-Europeanised.
One thing to keep in mind: horses today are not horses as they were when they were first domesticated. They've become vastly bigger. One big reason chariots mostly fell out of favor by the early classical period is that horses were now big enough that you could ride them and fight from them without needing an awkward and vulnerable chariot as a platform. Your Proto-Indo-European "horse nomads" are mostly charioteers at first
While the first two statements I agree with, the last one is not true. PIE speakers were riding their horses, and they had them pull their wagons; war chariots really only became suitable with the Sintashta, which is at a point where the IE languages had already diversified.