Basically, there are three Muslim civs - the names-keep-changing Caliphate in the east and al-Andalus in the west, and then the Turks come in late. There should also be about a 50/50 chance that Bulgaria ends up Islamic, and a smaller chance (~10-20%?) that France, Spain, Kiev, Portugal, Venice, Genoa, and Hungary do.
There was a Caliphate of Cordoba for a while (929-1031, according to wikipedia (I don't want to dig through books atm)), but if I remember right, there were serious objections to it being referred to as a Caliphate. Prior to that, it was the Emirate of Cordoba, which seems more resonable.
The map goes to the eastern edge of the Black Sea, which cuts out the Caucasus, Mesopotamia, and the Urals. While those regions are certainly important to Europe, it was generally agreed that they would shift the focus of the mod too far eastward and add another 1000 or so tiles of forestland in Russia that the AI would be irrationally desperate to settle. Baghdad is not on the map - Damascus or Aleppo is the easternmost city.
We've discussed representing the Mongol invasion as a change in the appearance/character of the Kievan civ, or as a massive barbarian uprising. Currently, I think the barbarian plan has more support.
jessicat, I like your revised list of independent cities with a couple of caveats. First, I'm not sure that we have room to do the Visigoths as an independent/nonplayable civ separate from the other independents. While there's certainly an argument for doing that, in that the Visigothic kingdom actually functioned more or less like a unified country, I'm not sure how many slots we want to fill or have active at a given time. If the game runs at a decent speed with the Visigoths in, that's fine. If not, I'd favor putting them under Independent-W. Europe. We're also not going to have Basque or Frankish civs, playable or not, so I'm not sure where that's going, and I'd argue strongly against having a Berber NPCiv. The operative idea for Iberia currently is that al-Andalus or whatever we're initially calling it shows up with armies in both N. Africa and Iberia. If we want to flip them a couple of independents in either place, that's fine, but there's a difference between making them strong and starting them out in ~700 AD with 8 medium-sized partially developed cities.