Hmm
How about a world without Christianity? I could imagine that the Roman Empire or rather, Empires - would have held together for a bit longer, but would still have fallen eventually. However, Europe after it would probably be quite different. As far as I know, Christianity helped some of the barbarian peoples to keep and create their own identities. Here, I think that the barbarian states would be assimilated by Roman culture, like it happens oh-so-often. In religion, I think that Roman Polytheism would continue to be important in Europe, but the eastern provinces would be filled with Zoroastrism and Mithraism (which will spread throughout the former Empire as well). I think Islam would still appear (here is another interesting idea, perhaps connected with the no Christianity idea, perhaps not what if instead of creating Islam Mohammed would have converted to Judaism as he once planned? Perhaps a reformed Judaism, with Melkhama Hakdosha instead of Jihad and with a more missionary attitude?), and will spread into the Middle East, but not as strongly as in the real history because that perhaps surprisingly, one of the things that allowed Islam to expand into Roman territory successfully was the well-developed Christianity, specifically the Monophisites. Also, I have read on some site that without Christianity, Neo-Platonism will become the dominant religion/philosophy.
As for political results, Id expect the following post-Roman world as of 500 AD (meaning the Mediterranean area as the others are not much different so far) to be a different one. I think that a Hun state will still survive, somewhere in Russia, Poland and Germany perhaps, while some pan-Latin barbarian states are formed in the former Western Roman Empire probably Arthurian Britannia would endure, as would Armorica. Visigothia and Franconia have benefited the most from Christianity, so they probably would be some sorts of primitive feudalisms with constant fights between different warlords, while allowing the cities to retain some of their culture. Ostrogoths or Lombards will probably have a pretty big and enlightened empire that would be quite, quite Roman in culture and to some extent in governing form. The Byzantine Empire would be stronger then OTL, and though without the Orthodox Church, it will still be a center of education, culture and intrigue. Maybe the Vandals would survive. I think that Arabs will probably seize Palestine and Egypt with Libya, but probably will fail to go farther if Islam will exist in this world. If it is Reformed Judaism, then well have a nice and big Judean Empire including the entire Arabian peninsula.