Having a great charismatic reformer of polytheism - like Shankara was for Hinduism - who didn`t interpret his role predominantly as a philosopher, like the Neoplatonists did, would help. Backed by Roman Emperors at the Empire`s height of power, such a Greco-Roman Shankara could have quickly caused quite a number of monastery-like institutions of this reformed paganism to spring up across the Roman world, and if you put a special stress on deities like Ceres or the Annona principle and have this pagan cult develop a mixture of bottom-up and top-down charity / social security networks like the Christians had them, you might actually have something that appeals both to the educated elites (some of who turned to Gnosticism, secret cults etc. IOTL, who might or might not be incorporated into the reformed paganism) and to the general populace.
Christians would not cease to exist, of course. But, if you revive polytheism in the given timeframe, you might find Christianity reduced to the size Buddhism has in India IOTL today. (And like Buddhism IOTL, Christianity could of course blossom outside of the cultural realm in which it emerged, e.g. in Aksum, in the Caucasus, in Arabia or Central Asia.)
You could always restore the balance later by having the Roman Empire collapse later and parts of it taken over or temporarily dominated by Christian polities.