Hyam MacCoby, a Rabbi, wrote a book called The Mythmaker: Paul and the Invention of Christianity that addresses at least some of your question. His contention is that Christianity grew rapidlty, not because it was something new, but because it was an ingenious blend of things that already existed. It combined the monotheism of Judaism, with the idea of an incarnate god (held by a number of "pagan" or pre-Christian religions), and the idea of a "mystery" (there were a number of popular mystery cults at the time).

Essentially, it was a mystery cult with a pedigree, so it appealed to people who were looking for something different, but not totally different.

Did you look at the follow-up comment(s) on the link you posted?

I actually have my own theory, and I want to see how you feel about it. The comparative advantage of Christianity over the many, many different religious sects milling around at the time, many of which stressed similar ideas of universalism and transcendentalism, was its exclusionary nature. One could join the Isis cult, or the Mithras cult, or any number of other similar religions, but once you did you could easily flow into other religious practices. Christianity, on the other hand, brooked no competitors, and so those who became Christian tended to stay Christian, and it could maintain its numbers easily while spreading.

And it's reply

I am not sure I would say that exclusivity was a cause for Christianity's advantage over competing cults, particularly the mystery/salvation cults, but I would certainly agree that it was a unique feature. The combination of universalism and exclusivism seems without an easy precedent.

It's also just briefly mentioned, but Paul was massively important in establishing the early Church with the gentiles.

I would think that my other comment, in addressing the ‘how’, at least touched upon the ‘why’. It is a little hard to construct an answer, because your question is engaged in contemplating counterfactuals and historical negatives – why didn’t a competing belief take over the Roman Empire?

By way of reply, perhaps we can consider some of the other possible contenders, and the religious milieu in which Christianity 'contested', and why perhaps some of the others did not 'succeed'.

Judaism

One of Judaism’s main advantages when it came to relations with Rome was that it was a religion with a homeland, an ethnos, and a long pedigree. Antiquity, not novelty, was respected, and the Jews had it in spades. This, alongside their rather stubborn monotheism, secured them a ‘place’ in Roman civic life, but always an uneasy one.

While these elements secured a place for Judaism, they didn’t make it likely to sweep the Roman Empire. Judaism was closely tied to a land and an ethnic people, and they were not, on the whole, very active in proselytising. To become a Jew, besides circumcision for males, was a major step that reconfigured your whole social identity and role.

And, given the Jewish Wars, the destruction of the temple, and the razing of Jerusalem, later Jew-Roman relations were even more tenuous. Messianic Judaism’s great dream was of a Jewish Kingdom, not to take over the Roman one. With the events of the late 1st and early 2nd century, the only real alternative to Christianity, within a Jewish sphere, would be the development of Rabinnic Judaism, which showed no movement towards active conversionism.

Traditional Polytheism

It’s actually a bit silly to talk about polytheism ‘taking over the Empire’, since in many ways it was the default. I suppose we could consider why, for example, Celtic Druidism didn’t sweep into vogue. I would put the answer like this: polytheism, of the Mediterranean kind, was very efficiently syncretistic. When your view of religion is that there are simply many gods, and what is mostly important is to appease them and to gain their favour through appropriate civic and cultic actions, then the appearance of some new gods doesn’t challenge your framework in any way. You either assimilate them as ‘a new set of gods’, or you integrate them as ‘oh, these are our gods with some different names’. Celtic polytheistic practices were unlikely to ever ‘take off’ in Rome, because those who might want to adopt them would likely simply incorporate them. Meanwhile, they would generally be perceived as ‘barbarian’ – far more likely to win adherence would be Eastern/Egyptian deities. But again, while the details may differ, I would argue that underlying such religions are some fundamental similarities that would mean not much changing at all.

Greek Mystery Cults

It’s pretty common to compare Christianity to the mystery cults. I think that comparison has some validity, but we should also note that there are significant points of dissimilarity. The mystery religions complemented, rather than competed, with polytheism, with the Imperial cult, and with philosophical traditions. As long as there is complementarianism of this sort among religious practices, the mysteries were never going to displace other religious practices as the dominant religious mode.

Furthermore, one of the mystery religions’ key facets was that membership was a closed-business. Initiation and secrecy were de rigeur. Christianity likewise practiced initiation and some mode of secrecy (in that the unbaptised were often sent out of the service before the Service of Communion), but there was an openness about teaching that did not match contemporary mystery cults.

I would also claim that mystery cults still built the majority of their beliefs off the mythic conceptions of the more general polytheistic counterparts. The difference between general polytheistic practice and mystery cults was in membership, initiation, and secrecy, not in fundamental teaching or theology.

Mithraism

I include a note about Mithraism because so many people think it parallels early Christian beliefs. I think the element that would always preclude Mithraism from becoming the dominant cult is that the evidence suggests it was an all-male mystery cult, and centered primarily among soldiers. Furthermore, like the other mystery cults, it showed no particular proclivity to spread broadly. Some (Renan, Boyce) have argued that Mithraism was a significant rival to Christianity, while others (Boyle, Ezquerra) have argued that either it was never that prominent, nor had the same aims as Christianity

Philosophical options

The third element of ‘religious’ options in the period would be the philosophical schools. These often functioned parallel to traditional religious practices, though conceivably some would be seen as rival systems of thought. I would consider Platonism (and its descendants, Middle and Neo-), Epicureanism, Stoicism (especially) as some of the main contenders in this arena. Stoicism in particular, in its cosmopolitanism, gives you the ‘universal’ dimension that parallels Christianity. Why didn’t Stoicism become the dominant mode of thought in the Empire? I think this is a counter-factual for which I can’t provide a good answer. Stoicism did have broad appeal and influence, but it was eventually eclipsed by Christianity.

In History of the Ancient World: from the earliest accounts to the fall of Rome, Susan Bauer makes a quick point that Emperor Constantine was searching for a way to unite his broad empire under a single identity, and observed that contrary to other religions (especially Judaism), Christians identified with one another regardless of their geographical location.

This is a quick and dirty way to explain why Constantine picked Christianity in an abrupt about-face of his earlier practices - a way to bind his sprawling empire together.

My main source is Robin Lane Fox, Pagans and Christians, but also some other readings.

A lot of factors contributed to making Christianity a small but very widespread new religion, but two in particular:

1. Rome had a bit of an inferiority complex because they knew that, as such things go, theirs was a relatively young religion and a relatively young culture. Judaism claimed to have a continuous religious tradition going back at least as far as Abraham, circa 2000 BCE, which, if true (and the Romans assumed it was) would make it one of the oldest religions on the planet. But it was very hard to convert to Judaism. Christianity was popular with intellectuals because it was a form of "Chaldeanism" that gentiles could easily convert to.

2. The funding to spread and found Christian churches, all over the empire, came from hacking a loophole in Roman inheritance law. Widows theoretically "inherited" their late husband's wealth and property -- but couldn't control or spend any of it, they could only hold it in trust for their next husband. The one exception was that widows could spend that money on donations to temples. According to numerous complaints from Roman officials, Christian bishops and priests offered widows this deal: liquidate your husband's business(es) and farm(s), donate all of that money to found a church, and we'll appoint you to be in charge of deciding how that money gets spent.

But "Orientalist" intellectuals, and widows looking to scam the estate tax system, were rare enough that, while Christianity was everywhere, nowhere was it more than a couple of percent of the population. Until ...

Well before the spread of Christianity, Roman government had improvised a form of checks and balances to protect against mad emperors: rule of the empire was divided between two or more co-emperors, each with their own armies. In the early 300s CE, Constantine got angry that his co-emperors weren't taking him seriously enough and decided to overthrow them and make himself sole emperor. But, as was the custom of the time, his troops wouldn't go into war without the blessing of the war by at least one priest, and what Constantine was asking was so radical and so illegal that no priest would bless it ... except for one Christian bishop.

Constantine won the resulting war, instituted rules granting huge advantages to rich and ambitious people if they converted to Christianity and only donated to Christian temples, and then ruled long enough that by the time he died, the other temples had been starved of resources long enough that there wasn't enough left of any form of Paganism to resuscitate.

Rodney Stark in the [The Rise of Christianity] (http://www.amazon.com/Rise-Christianity-Marginal-Religious-Centuries/dp/0060677015/ref=sr_1_1?s=books&ie=UTF8&qid=1401224259&sr=1-1&keywords=rise+of+christianity) argues that by the time Constantine declared Christianity the official religion of the Empire, it was already well-established.

He attributes this to Christianity's higher population growth rates, more secure communities and active proselytization.

The Church's position against infanticide and abortion resulted in higher birth rates and lower death rates. The latter because women took an active role in caring for sick persons as well the likelihood the women lived longer without abortions.

Higher security came from building more resilient communities that took care of their sick and poor in a time and place without charities or social welfare. Many persons found this attractive and would want to join.

Finally, Christians actively tried to convert others, using the established network of Jewish quarters in Roman cities. And, of course, St. Paul made Christianity easier to join than Judaism.

I would suggest Rodney Stark's writing on Christianity for this. I read some of his stuff over a year ago, so hopefully I'm remember his points correctly. Here is what I remember:

In the Roman Mediterranean, there was a tendency for people to 'shop around' for different cults and experiment with groups before eventually moving onto another cult. This was an accepted practice and even encouraged by some cults, as cults would often refer their members to one another, and relied on a constant influx of new members for money. Cult members would often belong to more than one religious cult as well. Christianity demanded sole and permanent adherence. Basically, Christianity was not hemorrhaging adherents.

Because you had to give up your ability to sample other cults, Christianity may have experienced slower growth at first, but its members were truly devoted. This is doubly true because of the occasional periods of state persecution that Christianity endured. While not all Christian adherents were the kind of people that wouldn't renounce their faith in the face of death or property loss, the public often witnessed the ones that were that serious about their faith. As a result, Christianity tended to attract larger amounts of people that were intensely serious about their favored cult. It also developed a reputation that made it stand out among other religious cults.

Compared to other cults at the time, Christian adherents could look forward to a clearly established conception of an afterlife. Christianity had a simple, but very appealing 'reward the good and punish the bad' approach to the afterlife. It wasn't the only cult that had a 'good' afterlife. Another example at the time may be the cult of Apollonius, but the faith that he inspired relied on philosophical explanations of an afterlife which may not have been as understandable or appealing to many.

Lastly, early Christianity earnestly pursued good works, particularly in the cities. To give you a point of comparison, while Christians were willing to aid the suffering in plagued cities, Apollonius' response to the appearance of plague in a city was to have the community stone a homeless man to death. Obviously the cult of Apollonius did not spread as rapidly among the poor and sick.

Since the cult of Jesus and the cult of Apollonius are often seen as third-century competitors to one another, I would suggest reading Philostratus' Life of Apollonius of Tyana. You'll see a lot of similarities between the two cults, but a few tales give a pretty clear picture of the advantages enjoyed by early Christianity. In one case, Apollonius is traveling to Rome and is abandoned by his entire entourage, who fear Roman persecution.

Would Christianity have spread as fast/successfully without the contemporaneous development of the codex?

Maybe part of its success was explained by all the benefits afforded to the first cult to be widely distributed by books. Maybe Christianity is the MS Windows of Mediterranean mystery cults.