As others have said before, this challenge is extremely difficult because the origin and centre of Christianity itself is in the East (The Holy Land, the First Churches, Four Patriarchs of the Pentarchy) so while you can get a WRE/ERE division (as a result of Diocletian´s reform, The Crisis of the Third Century or even the division of power between Octavian and Mark Anthony) without it implying that is too late in time to stop Christianity, you cant get a world where Christianity fails in the East, without it failing too in the more traditional, pagan West. A Christian West and Pagan East will be probably a temporal thing, based only in Cuius regio, eius religio, so the East will be considered pagan or the West christian because of the Emperor´s religion, not the real religious situation. The easiest way that I can imagine to get this is an early conversion of Constantine The Great when he was only the ruler of the West, and Licinius remains pagan but friendly because Constantine is protected by his own Edict of Milan, Edict that was co-authored by Licinius himself. The problem is that Constantine will try to reunify the Empire at any moment, and Licinius will try to maintain the Tetrarchy model by dividing his power by setting a Caesar, so his ERE would not be an ERE in the classic sense. Other possibilities are:
*Procopius, (Julian´s Cousin) is succesful in overthrowing Valens, surviving Valentinian I, gets a deal with Gratian and continues the policies of The Apostate. (However we dont know much about Procopius or the faith that he professed so is difficult to say how much plausibility this idea has).
*There is a Christian usurper in the West during Julian´s reign, that him (or a pagan succesor) are forced to get a deal with because the East is too occupied with the Sassanids to fight ANOTHER Civil War. (However, this will be only an armistice. Until Theodosius or Zeno, by fiction or fact, that phrase from The Romance of The Three Kingdoms applies:The empire, long divided, must unite; long united, must divide. (Of course, in Rome, long doesnt apply as much as in China).
*Constans survives and remains emperor of the West, meanwhile Julian the Apostate remains the Caesar and heir of Constantius II. That way, the West remains Christian while the East is under The Apostate. (More stable than the previous option, but again, it is not a guarantee of peace).