Arguably Christianity
was periodically legalized (or, at the least, decriminalized) before the Edict of Milan. The severe anti-Christian persecutions of emperors like Nero, Decius, Valerian and most infamously Diocletian wasn't a constant straight line, there were emperors who eased up on them to varying extents.
Hadrian for example actually instructed his provincial governors to carefully investigate accusations being made against Christians (therefore meaning he did not view being Christian, in and of itself, as a crime) and to punish the accuser if the accusation turns out to be false. Gallienus, who unfairly gets a lot of shit for the Crisis of the 3rd Century's nadir happening on his watch (even though it wasn't his fault and his hard work left Aurelian with the foundation from which to become
Restitutor Orbis in the first place), also greatly eased up on the persecutory policies of his predecessors and granted what is known as
the 'Little Peace of the Church'.
But if you are looking for an earlier specific, pro-Christian edict akin to that of Milan and one which will stick with the same longevity, your best bet is probably having
Philip the Arab reign for a lot longer.
He was exceedingly friendly to Christians by the standards of the time, to such an extreme that it's been seriously argued that he was a Christian himself, but he was defeated & killed by Decius (one of the harshest Imperial Roman persecutors of Christianity) after only five years in the purple historically. Let's say God gives Philip the chi-rho cheat code almost a century ahead of date and he proceeds to kick Decius's ass at Verona as Constantine would do to Maximian, then does the same to any other would-be usurper who comes at him. He even had at least one son,
Philip II, who was of course assassinated by the Praetorians the instant they heard he'd lost to Decius historically; in victory though, that means he has a hereditary successor available, and thus a chance (albeit far from guaranteed) to establish a 'Philippic' or 'Arabian' dynasty.
Well, a victorious Emperor Phil still has his work cut out for him. The Crisis of the 3rd Century is not in full swing yet (the worst of the era follows the reigns of Decius and
his successor, Valerian, historically) and Philip's reign was actually a rare oasis of relative stability between the Six Emperors, the inadequate and too-young Gordian III and then the downward spiral of those two; but many of the ingredients are there already like the out-of-control inflation, the chronically unstable succession to the purple, the devastating plagues, etc.
I suppose the best-case scenario is that a much longer-lived Philip keeps the Crisis from completely spiraling out of control: preserving the Romans' internal trade network from crumbling, suppressing all other usurpers before they can do too much damage, and keeping the many, MANY barbs swarming the borders from breaching & overrunning huge parts of the empire where Decius & Valerian had failed catastrophically - basically ending the Crisis earlier before it reaches the nightmarish, nearly empire-ending proportions that it did IRL, and then managing to pass his diadem on to Philip II at least somewhat smoothly. In which case he'd deservedly go down as one of the great Roman Emperors of history and, if indeed he was a Christian promoting Christianity long before Constantine made it cool, Christianity gets a huge credibility boost from association with him. The Roman Empire itself almost certainly lasts a lot longer without the Crisis being half as bad it got historically.
Probably won't be that easy for him or the Early Church though. I think it's likelier that the Crisis becomes even messier with a Christian religious dimension being added onto its already extremely volatile list of causes & exacerbating factors, certainly if Philip himself is a Christian. We don't know anything about Philip II (he died at age ~12), he could've been a genius, a complete moron, a benevolent monarch or a tyrant or anything in between. But I think it's probable that any attempt at establishing a lasting Arabian dynasty looks kind of like the Constantinian dynasty: lots of internal struggle (just against other usurpers instead of between dynasts, there's no indicator that Philip was as...prolific as Constantine or his siblings) between the still innumerable wars with foreigners and at least one serious attempt at restoring the old gods, it may even come from within the dynasty itself Julian-style if it lasts long enough.
Said old gods are almost certainly stronger and Christianity weaker compared to the situation immediately preceding the Milvian Bridge (Diocletian's persecution was was part of a broader effort to renew the traditional Roman values & spirituality as a unifying glue for the post-Crisis empire, with Diocletian having styled himself as a great restorer of ye goode olde times, and by this point Christianity's alarming growth certainly came in large part at the expense of the olden pantheon rather than the Jews, who were pretty much broken as a force after Hadrian's heated gamer moment in the former Iudaea). Also the Praetorians are still around, unfortunately for not just the Arabian dynasts but also anyone who likes stability and the Roman apple cart not being upset at the worst of times for the worst reasons imaginable. Assuming similar length of hostilities to the real Crisis and that the situation still ends in a Christian leader prevailing rather than a proto-Diocletian or some other religion prevailing (ex. Aurelian still taking over, living longer because Philip II or whoever annihilated the Praetorians early, and making Sol Invictus into Rome's #1 god instead), you would basically bring the Valentinianic-Theodosian religious situation of an increasingly dominant Christianity poised to become the Roman state church from the end of the 4th century to its beginning instead.
Whether it would be enough to avert the fall of Rome entirely is doubtful IMO, I don't blame Christianity for the empire's demise in the West as Gibbon (and a horde of Reddit atheists) does but I don't think it had a whole lot with the root causes of that either. Which IMO ultimately lay more in the Roman state's hollowing-out and the Roman ruling elite completely discrediting themselves, between the constant coups/civil wars even with the various barbarian invasions ongoing and the collapse of the economy as well as anything resembling economic opportunity to an increasingly unfree populace, to such a point where they couldn't muster up any reasonable arguments as to why having them crack the whip over your back would
really be any better than Großerschwanz the Chudgoth warlord (or at least his Romanized cousin,
Magister Militum Flavius Gigachaddus) being in charge. Considering both East and West were already Christian when one fell and the other survived for 1,000 more years, the Christian faith or lack thereof was probably not a decisive factor in their fates.
