With medieval Europe I consider the medieval European countries to be those under the control of the Roman Church and being part of Christendom.
Then where exactly do the pagan Norse, Anglo-Saxons, Irish, and Balts, Arian Franks and Visigoths, and Orthodox Slavs and Hungarians fit into this scheme? Western Asia?

Short version: you're wrong. Europe is a geographic region--its eastern borders are nebulous and its southeastern borders are ill-defined, but the Balkans, Slavic Eastern Europe, the Baltic coast, Scandinavia, the British Isles, France, and the Italian and Iberian Peninsulas are clearly a part of it. Meanwhile, the Middle Ages are a period arbitrarily defined as spanning the millennium from A.D. 500 to A.D. 1500. So during that period there were in fact Christians of at least three different sects (Catholics, Eastern Orthodox, and Arian Christians), Muslims, Jews, and several varieties of pagans inhabiting Europe, to say nothing of a variety of heresies like Catharism. Europe is not just its Romance, Germanic, and Celtic inhabitants.
I always thought that the Byzantine empire was a rival to the western church with its own Orthodox Church, beliefs, culture, and heads of authority.
Yes and no. The history of the relationship between the Roman Catholic and Eastern Orthodox Church is complicated, and, unlike the Oriental Orthodox Churches, there wasn't a complete split between the two until the High Middle Ages. Even after the Pope and Patriarch of Constantinople mutually excommunicated each other, there were occasional peace feelers from one side or the other. Also NB that the Eastern Orthodox patriarchs acknowledged the Patriarch of Rome (the Pope) as "the first among equals" but not the head of the Church. So again, there was rivalry but also sometimes cooperation. Recall that the First Crusade was instigated when the Patriarch of Constantinople sent out a plea for help to the Pope (it didn't turn out as he planned), as was the Fourth (which
really didn't turn out as he planned and was essentially the final breach between the two). Also NB that the Eastern Orthodox Church was (and is) less centralized than the Church of Rome. That's why you have one Pope but many Eastern Orthodox patriarchs with their own autocephalous churches (Greek Orthodox, Bulgarian Orthodox, Russian Orthodox, etc.) but common theology. Same situation among the Oriental Orthodox, albeit the Coptic Church has a pope (who, again, is the first among equals as the Patriarch of Alexandria, taking the place of Rome after the Council of Chalcedon, which the Oriental Orthodox churches rejected as invalid).
And with their geographical location (of the empire overall) they seem to not be completely European and not completely middle eastern but something in between. This is why I think the inclusion of the Byzantines could be really cool as the civ would be a hybrid of European and Asian influences. This could be shown in the leaders clothing, the music and the unit and city design.
I mean, yes, the Byzantines were influenced by the Middle East...as was Classical Rome or Medieval Spain (al-Andalus, anyone?) or Victorian England, but that doesn't make them less European. They wore silk because they smuggled silk worms out of China, for instance, and their chanting sounds Middle Eastern because Christian chant has its roots in Judaism and was then further influenced by Syriac religious music (and this applies to Western Christianity as well). And much of the Middle Eastern influence in the region comes from six centuries of
Ottoman rule. So yes, sure, they have some Middle Eastern influences to their culture--no culture can be wholly uninfluenced by its neighbors--but thinking that makes them not European is to take a very narrow view of Europe and suggests that Spain, Rome, Greece, and England are also Asian civs--they were no less influenced by Asia than the Byzantines, after all. (Spain by al-Andalus, Rome and Greece by the Middle East [Aphrodite is a Semitic goddess, Poseidon might be Berber, Hermes got syncretized with Egyptian Thoth, etc.], England by India and China.)
It would also be really interesting to have them on the real world map as their location would allow them to benefit from several trade routes and militarily control access between the two continents.
Which was both their strength and their ultimate downfall, but also has nothing really to do with whether they're European. (And if it sounds like I'm arguing against including the Byzantines, I'm not. Despite being sick of just how many Greek civilizations we have in the game I really
do consider Byzantium essential and really wish I could jettison Alexander, Cleopatra, and Gorgo in their favor. I'm merely pointing out that culturally, religiously, historically, geographically, Byzantium was definitely European.)