So here are some of my predictions off the bat.
Catholicism spreading to the Sahel and West African Kingdoms like Mali and Ghana. (Via Berbers)
Christianity I can see, but it might not necessarily be Catholic. Mauretania (a key point for the origin of West African Islam) was relatively untouched by Roman culture and Christianity unlike the rest of North Africa. OTL the area had a unique fusion of Berber paganism, Judaism, and Islam at one point. I wouldn't be surprised if similar events happen here, which would affect how West African Christianity develops. There's also the secondary concern of communications. Yes, it wasn't so bad for the Church of the East to communicate to its many distant followers, but the harsh coast of West Africa combined with the Sahara will deeply affect how the Church evolves in that area.
Ethiopia/Axum being a regional power in the Indian Ocean.
Axum collapsed due to climate IIRC, so it's heyday might only be a few centuries before it's replaced by another regional power (i.e. whoever controls Yemen). Yemen might end up Christian thanks to Axumite influence, which would have a major impact on East Africa and South India.
The Swahili coast adapting Syriac/Coptic Christianity from Axum and whatever (likely) Christian Arabian state/s emerge. Along with most of East Africa getting absorbed as a new fringe in the greater Christian world.
Probably. It would be interesting to see their alphabet (Ge'ez or Aramaic based?). I'd argue that Southern India will be a major influence too, since stronger Christian influence in the Indian Ocean likely means stronger St. Thomas Christians and perhaps even a Christian state there (easiest might be the Maldives).
Any chance for Zoroastrianism, Buddhism, or another religion to exist as a minority on the east coast?
Depends what goes on in India here.
Could Christianity spread a little deeper into Madagascar, and the southern and lake kingdoms of Africa?
Madagascar I can see since it was influenced by Arab culture (their precolonial writing system for instance) and Islam in parts. Maybe an ambitious ruler could begin the process of Christianizing the island through conquest. I doubt the Bantu kingdoms in the Great Lakes or southern Africa would be Christian for a while.
How connected culturally, technologically, and politically will these alternate African states be with everyone else?
More than OTL but I doubt too much more (at least with Europe/North Africa). It's just too remote given the rough seas and the Sahara. Ethiopia on the other hand will be much more connected since they aren't a Christian outpost (well, along with the Nubian states--I'd really hope for a second "Kushite" rule of Egypt to get the province out from under Roman domination) in a sea of Muslim states. A lot of the same economic conditions from OTL still apply, we've just changed the religious/political aspects of it.
Many parts of Africa are going through struggles related to Islamists and related terror attacks, so that's something that wouldn't exist now.
Aside from the global financing some of those groups get, if Africa is still as messed up as OTL you'd still see a lot of problems with terrorism.
Lets try another slightly more plausible scenario, Hmm it the native Berber tribes who were nominally Roman citizens and client states manage to beat the arab invasions back the old african Roman provinces could become independent ans combine with the Berbers with them developing in nearly the same way as the eastern Romans having an actual border with the Caliphate meaning these two states manage to insulate muslim expansion into Europe meaning the Visigoth spain which will retain its roman inspired culture for far longer with the old city of Carthage becoming the Southern Roman capital
The logical border with the Caliphate is the desert coast of the Gulf of Syrte. This is a difficult frontier to invade through, and the Gulf of Syrte itself is known for rough sailing conditions (and you will need naval support here). So the threat is of a different nature (in terms of how it would be dealt with) then what the ERE faced. Then there's the nature of North Africa itself in the early 7th century which was an utter mess politically, basically Romano-Berber states (of varying degrees acculturated to Roman culture, including Christianity) nominally ruled by the ERE Exarch. The logical development for North Africa would look more like France, Italy, and Western Europe, with Carthage serving as the main cultural and economic center which might raise up a powerful king to conquer/subdue most of the territory. This leaves out the very interesting case of what might happen to Mauretania south of Tingitania, which will be integral to relations between sub-Saharan Africa and the Mediterranean world. It isn't likely to permanently be subdued by Carthage, nor is it likely to be conquered by the Visigoths in the meantime (whose state was a political mess).
Given the huge influence of the Berbers and the fact that various heresies gained a following at times in both Christian and Islamic Berbers and the attestation of Berber Jews and pagan syncretism into Late Antiquity, it's highly possible that a new Christian heresy emerges (if not another branch of the Abrahamic faiths) which will influence sub-Saharan Africa and any Christianity there.