With the fall of the eastern centers of early Christianity early on, and the eventual fall of Constantinople, the eastern Christians were rather limited in their ability to proliferate aside from the slavic peoples. However without the expansion of Islam could the eastern churches have grown much out east in central Asia in the place of Islam? Perhaps a christian version of the Mughal dynasty in India could have popped up lol.
Hinduism predates Islam and Christianity by centuries. I think if Islam were to be just a figment of imagination, Hinduism would be the big winner. I know that doesn't answer your question, of course.
To your question, I think Catholicism would have a larger base, if only because Orthodoxy would still be competing with the Eastern religions in the Middle East. North Africa, however, would more likely become Catholic than Orthodox.