(This is assuming Christ exist, and Christianity isn't the result of Paul fabricating him)
There were several 'Messiah's hovering around Palestine at the same time as Jesus was, and several of them were rather similar, before they were assimilated/annexed by Christianity. However, most of them were Jewish Revolutionary-type groups, which would have trouble (obviously) becoming Gentile groups.
But wait! Christianity kept competing with other groups for power in later centuries. I'm not so sure that Mithraism couldn't become the dominant religion. After all, OTL it kept women and slaves out, but it could easily have mutated - it already had before in order to become the religion of Sol Invictus. Actually, that suddenly put to my mind some religious war between Orthodox Mithraists and Protestant Mithraists. Cool.
But I digress. The most likely thing to be seen would probably be some sort of Neo-Platonist religion coming out of Rome, assuming that butterflies didn't cause it to adopt something we've never heard of or the Viking religion.
Probably outcome? The Roman Empire lasts another, say, century or so, and the Dark Ages are nowhere near as bad as they were in our timeline, since the transition would probably be smoother with the cult followed being a Roman cult rather than a foreign one. That's not to say that for peasants at the bottom it wouldn't probably be more difficult and violent than OTL. Impossible to say, with such a far-back PoD.