Having thought some more of the Celto-Slavic Europe scenario, I have decided that it has great promise. Some more development is in order, ofcourse...
Firstly, we should establish some basics. I still think we shouldn't have a Roman conquest of Britannia, to make sure that the Celts remain strong enough. Germannia however will be conquered, and the Germannics, apart from those in Scandinavia, will be marginalized and later swept aside by steppe invaders, to be eventually finished off by the Slavs.
Also, as something of a butterfly effect, the more overstretched Roman Empire could die earlier (i.e. in the 3rd Century; Diocletian and other "Illyrians" were a considerable stroke of luck, i.e. improbable, though possible, by definition). I even have a more rational explanation - Germannics fleeing north will disturb the Scandinavians, the Scandinavians will in turn attack Britannia, and the Britannians will then take advantage of Rome's long Gaelic coastline, even less defended than usual due to the civil wars, and invade Gaul. Meanwhile, the Slavs will be pushed from the east by the steppe peoples (a constant factor), and invade Dacia and Germannia. And, ofcourse, the new, vigorous Sassanids will advance into Roman Asia (as in OTL, but more succesfully due to the general chaos), and Berbers will attack North Africa. And through it all, warlords will fight for the Roman Empire; sure, promising leaders will emerge and maybe will even come close to saving the Empire, but it will be too late. Plus the best of them will be gunned down by hitpolarbears.
So in the end, we will have separate Roman successor states in Hispannia, Italia, Graecia and North Africa, a Sassanid Empire in control of the Middle East (I'm thinking roughly Achaemenid borders in the west, including Egypt and Thracia), Celtic tribes and petty kingdoms in Britannia (those who had warded off the Scandinavians in the end) and Gaul, and Slavic tribes east of the Rhine and the Alpes (and north of Graecia - although I suppose they might conquer it, it would be quite interesting to a Slavic Greece, as Lord-Hegemon Krichevskoy will actually become plausible). Gradually, Slavic states will appear, but its quite hard to predict the exact configuration. Lastly, Germannics will held out in Scandinavia. The Bosphorus will be intersting - the Goths might actually hold out there, and become as Vikings for the Sassanids.
The Sassanid Empire will fall at some point, ofcourse. Arabs, Goths, Turks and rebels (especially Coptic Christians (I know they didn't split as such yet, but IMHO it is quite inevitable that the Egyptian Christianity will branch off from the other ones, especially with it being in disarray after the sudden fall of the Empire and the ensuingchaos)) will tear it apart. Also, one of the Roman rulers might rebuild the Empire - I think it will be especially ironic if the North African ruler, whose capital will naturally be Carthage, will be the one to reunite the Latin parts of the Mediterranean. Not sure about how viable that empire might be, but if the Byzantine example shows anything, then the "Carthagine Empire" might live on for millenias, as its geopolitical situation is considerably safer than the OTL Byzantine one (the Berbers aren't quite the same as Arabs, their population is much more sparse and spread-out. Then again, we DO have the Almoravid example...).
Particularily interesting is religion in this world - in Roman states, Mithraism and Christianity will compete, but Christianity's best opportunity in this world would be Egypt if the "Coptics" act fast enough when the Sassanids collapse. Egypt will be in position to take over the Red Sea, after which "Coptic Christianity" might take the niche of OTL Islam in the Indian Ocean (i.e. it will spread into East Africa, South India and Indonesia). The Celts might as well eventually adapt Christianity, in fact that seems quite likely, but it will be radically different from the Roman one. Slavs are more interesting; they will come under Roman Christian and Zoroastrian influence, and the southern ones will probably convert to one faith or another; the northwestern ones will be under Celtic influence, and will join the Celtic Church, most probably. The eastern ones, however, might form something else entirely. After all, Slavic Polytheism in OTL had good chances of replicating the Hindu success (there are lots of parallels between Hinduism and Slavic Polytheism anyway), and OTL attempts were made to turn it into an organized religion. Here, under even stronger Iranian influence than in OTL, there is a chance that such efforts will succeed...
Still, that's a pretty rough draft.
---
Separately from that, an altgeography idea - we already had a smaller/nonexistant Mediterranean Sea, but what about a Mediterranean Ocean (with a natural Suez Strait)? Sadly I am not all that good at this kind of althist, but we have some people here who are, so what do they think?