Would Orthodox Cumans (etc.) be any likelier to develop something more organized than they had already, or are they going to remain as nomadic as they were as pagans?
If still on the steppes, I mean.
I think the Pontic steppe and westwards almost precludes full nomadism, but it's hard to say. The Pechenegs looked like they were settling, then the Cumans uprooted them and they started up raiding as a whole nation again until the Byzantines/Cumans/Hungarians ended them.
The Tork (Ghuzz)/Pechenegs that lived next to Rus (Black Hats) became properly settled and an important source of support for Russian princes vs. their cities and vs. each other, so it's not out of the question.
There were also plenty of towns on the Russian Steppe, populated by (probably Turcified) Steppe Alans left over from the Khazar era, which were then used by the Cumans (the Sharukan', Sugrov, Balin and Cheshuyev in the Chronicles) as forts/trade posts/winter residences.
Vladimir Monomach's expeditions sacked all of them in the mid-12th c. and threw the Cumans back to the Volga for a generation, though, so it's hard to say.
That said there were LOTS of settlement going on at the time. Volga Finns (Mordvins and Mokshans) were starting to coalesce somewhat, Volga Bulgars were spreading south along the Volga, the Cumans were settling Alania and intermingling, Russians of course were colonising the river basins very rapidly.
There was also likely a string of towns on most of the major river crossings all the way to the Irtysh.
The Mongol invasion however levelled all of those things and disrupted things immensely (Russian crackpot Eurasianism and whatever other silly theories notwithstanding, the archeology is pretty solid).
There was a burst of urbanisation in the early 13th c. under the Golden Horde (Volga Estuary, Don, Volga Bulgaria, North Caucasus, Dniepr Crossings, Crimea, Dniestr - all the usual places basically) but by the end of that period Timur went and sacked and slaughtered his way pretty much over the entire area. Whatever wasn't taken by Lithuania remained ruined with few exceptions until the late 15th c. when Muscovy, Crimea, Lithuania and Kazan became stronger.
The Steppe itself wasn't settled to 13th c. levels until the Russians built the last big defensive line in the 1650-1670s (not counting the Kuban and Grebensk lines of course, I meant just the Don/Donets area).
So without the Mongols, most other nomadic nations were probably going to increasingly rely on permanent focal points. They were destructive of course (as were the Russians on occasion) but the Mongols were something special in that regard.
