The problem for an emperor is there were several flashpoints in the mid-Empire: Germany, the Danube, Mesopotamia. He could take charge of one army but the other two (or more) spots would require he give a general command of a lot of legions. And a general with an army is a usurper in waiting.

The tetrarchy was an attempt to fix that by appointing a junior co-emperor at first and then expanding it to a total of four emperors each with their own army covering the four hot spots of the empire. The idea being that the senior Augusti would retire and the junior Caesar would be promoted to Augusti and two new Caesars would be chosen, etc... However the system broke down immediately following Diocletian's retirement as Maximian was unhappy at getting forcibly retired and Constantius wanted to pass power down to his son Constantine. A nice idea but couldn't deal with ambitious men.

It’s funny that you end with the acknowledgment that you’re straying into questions surrounding the empire’s collapse, but in many ways any comprehensive answer one could possibly give you will ultimately end up hitting upon ideas deeply related to that larger question. That's simply the nature of late antiquity. Studying this period becomes in many ways a study of crisis management and response. --- Anyway, to your question:

It sounds like you’re generally familiar with the 3rd century crisis so I’ll just add a few quick items of history before diving into ideas more open to interpretation. First, the practice of delegating command in the way you're describing fits best with Diocletian, and it was a policy of immediate necessity. The instances of co/semi-co rule that pop up from time to time (Aurelius/Verus, Caracalla/Geta, Constantine/Licinius, and others) can for the purposes of answering your question be written off as off as unrelated -- especially those which occurred prior to the crisis in the 3rd century, which all had more to do with the issue of succession than anything else. None of them symbolize the political sea change that the Tetrarchy represents. Truly Diocletian's reforms can be said to have brought about the death of Augustan Rome.

Anyway, if we establish Diocletian’s stabilizing reign as the nexus from which moving forward in time reveals the official bifurcation of the empire, it's rule by co-Augusti, and the consequences resulting thereof, and moving backwards (pre-crisis) we see the Principate alive and well with the same area ruled by one person, your question of "what changed" is a good one. Why were subordinate emperors needed when things were fine with just one for so long? The answer is both straightforward in one sense, and deeply complicated and very difficult to answer in another.

It's straightforward in the sense that, as you mentioned hearing people say a lot, the whole thing became simply too much for any one man to handle. The bureaucracy had collapsed. An endless string of wars and false claimants became so normative that a child born at the end of the Severen dynasty would live a lifetime with this situation providing the total framework of what it meant to be Roman. With Roman traditional government so broken and its institutions so deeply poisoned, Diocletian brilliantly recognized that the old game of being declared sole emperor and making it true by beating the armies of rivals wasn't going to cut it anymore. He needed to change the rules. By bringing on co-rulers he addressed two problems at once by mitigating the threat of usurpation and also dividing responsibilities, thus ensuring that the countless major problems plaguing the empire could each be given the appropriate amount of attention.His plan worked. He maintained his rule longer than anyone had in decades and stability was restored. Restored, that is, until he stepped down and the families of the other three tetrarchs started a new round of civil wars...But this period notwithstanding, it has to be stated unequivocally that Diocletian's reign did bring about the first period of real political stability in decades and effectively bought the empire a new lease on life.

Now if we move back in time to, say, the Nervan-Antonine period (which given both its proximity to the period of crisis and its presence within the cultural consciousness as the period most commonly associated as the "Pinnacle of Rome" makes it a good era with which to compare), and try to suss out what exactly was going on at that period that didn't demand multiple rulers, what we find is a political, cultural, and economic society that by and large ends up on the positive side of all those different scenarios you asked about in your second paragraph:

For one thing there weren't many attempted insurrections or conspiracies (although the letters of Trajan reveal that to some degree conspiracies similar to those we read about in the julio-claudian period did still occur, but the details are lost to us). What we can conclude from this is that, for the most part, the aristocracy was content with their situation. They were getting their due and didn't feel the need to mix it up.

We also find a more integrated, less locally focused, Roman world that enjoys stable and vibrant trade and cultural exchange. To use your examples, movement between London and Alexandria was indeed relatively safe, although aside from traders I can't imagine that an Alexandrian would ever feel the need to head up to Britain. Contrast this with the period in the 3rd century when people do start to look inward and become more local in their thinking, even to the point that little mini-roman kingdoms start popping up in Gaul, and the full-on break-away Palmyrene empire shows up in the east. (As a side note, this idea of local thinking is useful in understanding the character of the middle-ages. Given the stark contrast between high-antiquity and post-Roman europe, it's an interesting concept to think about.)

In sum, things are just stable. People for the most part believe in the stability of the system and trust that it works. A good example to illustrate what this means in practical terms can be found in the Book of Acts. It is no trivial point to note that when St. Paul is beaten by the local magistrates and shouts out, “I’m a Roman citizen!" they immediately stop the abuse and send him off to Rome because the law states that as a Roman citizen Paul has the right to trial before he can be beaten or killed. This story is indicative of the political stability enjoyed by people pre-crisis. In the same way that Americans can (for the most part) expect to have the police arrive when they call 911, so too does Paul have the expectation that his system works. Remove this civic faith from society over the course of a 50+ year period and it becomes difficult to see how it can possibly be nursed back to health. This is as true for us as it was for them - a fact that, for me, makes Diocletian's job is all the more remarkable. He simply understood that given the degree to which things had decayed it would be more than any person could handle alone. In that sense, it's not just scholars saying that that's what happened. It's an idea that Diocletian himself came to understand.

This is, of course, a very simplified explanation that can really be reduced simply to me saying: stable/unstable. The reality is that whole books and fields of research can be (and have been) devoted to any specific individual institution or component of Roman society over the course of the centuries. Their civilization, like ours, was highly complex with its myriad parts integrated in all sorts of ways. In order to get a satisfactory answer to your question, each one has to be examined (as much as such a thing is even possible) in relation to the others.

I'd just point out that the tradition of co-emperors is much older than the crisis of 3rd century. Even the first Emperor Augustus had a co-emperor in the last two years of his reign - Tiberius. Obviously, the reason for that was to ensure the smooth transition of power. There were other examples of imperial colleagues before the crisis of the third century, but it was the crisis when it became critically important to ensure painless transitions, as the office of the Emperor became increasingly unstable. The reforms of Diocletian went even further in the same direction by introducing the concept of two senior emperors (Augusti) and two junior ones (Caesars) although in practice it didn't really improve the situation.

The first emperors worked in a different system to that of the later emperors. This system change was in part due to changing internal and external sources. Internal changes that contributed to this were numerous. During he Augustine Dynasty the successors were supported that was built by Augustus to keep the empire running and it worked so well that it survived his death. Nero screwed it up so much that he ended the dynasty. The way of becoming emperor during the Flavian and Nerva–Antonine Dynasties was usually through appointment. In the cases where it was passed to a blood relative the emperor ended up being the end of the dynasty (see Domitian and Commodus). The important thing to note about all three of these periods is that none of these emperors ruled/ made the empire run by themselves outside of Augustus, who was a brilliant statesman. There is evidence that Tiberius had power stolen from him by the head of the praetorian guard at one point. Marcus Aurelius and Lucius Verus ruled as co-emperors far before the actual division of the empire into two pieces. Later emperors in many ways expanding on already existing themes in the empire. Constantine also basically made the empire into parts because the empire couldn't have just one man in charge had become apparent. It should be also pointed out that in many cases the later emperors would appoint a lackey or close blood relative as the emperor in the east, power lay mainly in the west until its decline.

While the legions did show increased support for individual generals this was not actually a new occurrence. Many generals had used their legions to control Rome before (see Sulla and his dictatorship). This problem reemerged during the empire as numerous different threats were constantly on Romes borders. The roman emperor would often have to give a general command of numerous legions to put down these intrusions or rebellions. These generals could then turn around and try to take the the "throne" themselves. The spiting of the empire did lead to two different rulers the main power still consolidated under one of the two emperors, except in the tetrarchy. If you want to read more on this topic I would suggest either the Cambridge ancient history series on Rome or Peter Garnsey and Richard Saller * The Roman Empire Economy, Society and Culture*. Hopefully you find this helpful.