It's possible to see both maximal (Justinian's Flea) and minimal (The Making of Orthodox Byzantium) interpretations of the impact that the Plague of Justinian had on the empire. Currently, I tend rather towards the more minimalist interpretation. Justinian's Western wars took so darned long not because of the plague, but because of his refusal to spend much money on them. The grand strategic balance with Persia, equally, was pretty much unchanged in 550 to what it had been in 530. Mediterranean trade was as busy in 600 as it had been a century before, so it's difficult to find much room for the plague here.
Nonetheless, the state definitely seems to have been short of money by the time of Justinian's death, and his successors, especially Maurice, apparently found it difficult to raise more cash. If we accept the notion that Justinian's Western wars were relatively cheap in the long run, it seems clear that the reason his successors were unable to build up an Anastasius I style surplus is because of a reduced population due to the ravages of plague. So, perhaps one direct POD of a plague-free ERE is a more prosperous 550s. It'll be much easier to bribe the Slavs and Avars, so the Latin core of the Balkans likely does not come under sustained attack in the latter part of Justinian's reign.
The Italian war may be won somewhat earlier if one believes that Justinian's competent cousin Germanus died in 550 of the plague- but not massively so, and the damage will have been done to Italy. Nonetheless, if the Empire has more cash to throw about, it's likely able to prevent the migration of the Lombards into the peninsula, or, at worst, make sure that this happens on terms reasonably favourable to the Empire. Italy thus gets a good twenty or thirty years at minimum to recover from the Gothic wars. Without the plague, recovery will come somewhat more quickly, though this probably shouldn't be exaggerated.
The apocalyptic tone of the times was doubtless heightened by the plague, so, without it, Church politics will be impacted. Whether these flaps of the wings of small butterflies go on to create hurricanes cannot be foreseen. Personally, I think it's likely that the Empire will go on as before- with vocal minorities denouncing the "heresy" of others, while the great mass of the populace carry on with very little awareness of what exact "heresy" they are supposed to be professing.
Basically, I'd say the Plague of Justinian sparked a series of small PODs, the results of which were probably not immediately clear to the Romans of Justinian's day. A world without it is not guaranteed to be radically different from OTL.
