As for the two empires, the relevant question is in the reverse: what must change with them so that they keep the Khalifas stuck in Arabia?
My obvious answer is their last war should be shorter and less even. Then they're not both exhausted when the Arabs attack.
It would still probably spread to Indonesia and central India via Trade though.
How would this affect the Sassanid and Byzantine states, more specifically.
they would reach India and China too.
Perhaps Ali disputes the succession of Abu Bakr and there's an early fitna?
Probably Nestorian Christianity will be more widespread than OTL. There were many converts in Persia at the time, and they would reach India and China too. While I'm not sure how sucessful they would be the Eastern Church will remain a greater voice within Christianity.
The consequences to Christian Europe's attitude towards infidels will be major, no crusades, no mass invasions from seemingly nowhere to feed paranoia and xenophobia (at least in the south, northmen could still happen and fuck over the Anglish). Not to mention that Charlemagne never comes to power, that means much of north germany is much strongly pagan than OTL, seeing as no Battle of Tours to feed the Carolingians standing amongst the Franks. Visigoths survive, that keeps the balance of power in the West mediterranean from swinging too far to the Franks. Rhomanion is able to recover their man power and hopefully rebuild Italy following the Gothic War.
The Arab invasion was by no means an inevitable event, it may have been improbable for nothing to happen, but all you have to do is keep the Caliphs from pulling the trigger on a mounted military effort.
But to answer the question, Islam spreads by trade if at all. More indonesia like conversion rather than the more conquest driven conversion of OTL. Christianity remains in dominance in Africa, possibly spreading into West africa, same goes for Kilwa and the rest of Africa's East coast.
The consequences to Christian Europe's attitude towards infidels will be major, no crusades, no mass invasions from seemingly nowhere to feed paranoia and xenophobia (at least in the south, northmen could still happen and fuck over the Anglish). Not to mention that Charlemagne never comes to power, that means much of north germany is much strongly pagan than OTL, seeing as no Battle of Tours to feed the Carolingians standing amongst the Franks. Visigoths survive, that keeps the balance of power in the West mediterranean from swinging too far to the Franks. Rhomanion is able to recover their man power and hopefully rebuild Italy following the Gothic War.
So, so much to think about if the Muslims just stay in Arabia. None of this even scratches the politics in central asia with a surviving Persian Empire.
Catholics were quite happy to pillage pagans, Jews and Orthodox Christians in our timeline. I imagine they'd see the Eastern Church as much more of "the other" in the absence of Islam.
All of that, plus the technological butterflies. The arabians made great leaps in math and science, and helped to keep some roman knowledge alive. We may be significantly behind tech wise unless someone in ATL take their place.
It wasn't called fitna, but Abu Bakr had to fight to reassert his authority as Muhammad's successor.*
* Some historians, most notably Patricia Crone, have raised doubts of the historicity of Abu Bakr's caliphal tenure. I don't think any argument on the point particularly compelling, but I use to this note that in our understanding of early islam there are some quite significant problems.