u/OldPersonName provided great information and links to lots of other great information. I just want to jump in and provide some input on a few things they did not mention.

One thing that just does not get enough discussion in traditional accounts of Alexander's conquest is the relatively recent political changes in the Achaemenid Empire that greatly assisted his initial invasion and conquest of western Anatolia and the Levant. The first half of the 4th Century BCE was marked by a series of rebellions in the western edge of the Persian Empire. Most famously this included the so-called "Great Satraps' Revolt" in the reign of Artaxerxes II, but that was followed by a series of other local revolts including two in Cyprus, one in Phoenicia, and another handful in western Anatolia early in the reign of Artaxerxes III. These were also aided in no small part by the precedent of Cyrus the Younger and support from newly independent Egypt in 401 BCE.

Since Xerxes retreat from Greece 80 years earlier, the western satraps had been given significant leeway to recruit and maintain their own armies as a defense against Greek raids. This policy also proved to be a useful tool when the Great King could deploy loyal satraps against rebels without having to go through the effort and expense of organizing a full royal army. By Artaxerxes III, the policy had outlived its usefulness. Greece was settled into a more-or-less peaceful entente after the Corinthian War, including the King's Peace that made them all swear to stay out of Persian affairs, and the rebellions early Artaxerxes III's reign prompted him to strip those military privilege's from the western satraps.

This was compounded by defeating revolts in Cyprus and Phoenicia, traditional bastions of the Achaemenid fleet, and spending most of the late 450s and early 440s redirecting resources toward campaigns in Egypt under royal supervision. This was a massive endeavor that leaned heavily on the resources of the Empire's western coast. Before putting this drain on the region and directing military attention to the south, Artaxerxes made sure that Greece was still in check. Sure Macedon was on the rise, but that wasn't seen as a pressing concern, and Artaxerxes concluded new treaties of friendship with all of the major players in Greece including Athens, Sparta, Thebes, and Macedon. Artaxerxes III completed the reconquest in 339 and was assassinated within the year.

As the last year of Artaxerxes reign played out, he may even have realized his error in leaving the Greeks unsupervised because Phillip II took Artaxerxes' distraction in Egypt to conquer most of southern Thrace, including an aborted invasion of the area around Byzantium, which was sort of Persian territory. Exactly how much control Persia had over the far side of the Sea of Marmara fluctuated, but they always tried to maintain some level of soft power there.

The next few years saw a flurry of activity where Phillip invaded the western coast of Anatolia to "liberate" the Greek cities, only to be assassinated in 336, just a few months after the Persian King Artaxerxes IV was assassinated as well. One of Darius III's first actions after securing his throne was to send an army to repel the Macedonians that were still sitting in his territory. The Macedonian army was disorganized and demoralized immediately after Phillip's death and was soundly defeated. Darius's forces were also occupied in Egypt at the same time. An new rebel Pharaoh had taken power there during the chaotic reign of Artaxerxes IV and was only defeated in 335, once again draining the military resources of Phoenicia and Syria.

There is some speculation among Achaemenid historians that this gave Darius III a false impression of Macedon's capabilities, and when Alexander launched his initial invasion, Darius didn't think much of it. He left it to the local satraps, who were soundly defeated at the Battle of the Granicus, giving the Macedonians a head start to work though western Anatolia while Darius scrambled to get an army together.

Of course that army was defeated at the Battle of Issus, which forced Darius to retreat and once again go through the time consuming, expensive, and often unpopular process of gathering another royal army while Alexander tore through the Levant which was just coming down from almost 30 continuous years of war either against the Persians and Egyptians. As OldPersonName pointed out, Egypt just welcomed Alexander with open arms, essentially gambling that a this shift would be better than continued Persian rule after Artaxerxes III and Darius had imposed harsh penalties for their recent independence movements.

So Alexander made it all the way to the Battle of Gaugamela with one battle against the full force of the empire (at Issus) and picking his way through the exhausted western territories at an extreme low point in their military capacity. The Macedonian victory at Gaugamela shifted the dynamic. Darius III retreated to the northeast while Alexander pushed to the southeast. Babylon and Susa put up no fight at all, essentially looking at Alexander's successes and deciding it wasn't worth a siege. Once he was in the heartland, the region with all of the royal palaces that identified capitals, there was once again and issue of resources and preparedness on the Persian side. These just weren't places that planned for major hostile armies. Since the time of Darius I almost 200 years earlier, you could count the number of rebellions or invasions that had affected the imperial core on one hand. They just weren't ready for something like this.

By the time Alexander was leaving Persepolis in flames, he had defacto control of half the empire including almost all of the regions that would normally be used to draw up heavy infantry in the Persian army. Based on the route he took in his flight after Gaugamela, it seems like Darius III was trying to put distance between himself and Alexander to regroup and bring the fight into a region where the Persians could take advantage of light skirmishers in the mountains and cavalry in the valleys, but he was killed by Bessus/Artaxerxes V and it just never materialized.

Alexander's progress through northern and central Iran was a slog. He faced far more organized and constant resistance from the various Iranian peoples and satraps than he had seen in the west, but by then Alexander controlled the treasuries and resources of the wealthiest and most fertile parts of the Persian Empire. There may also have been a false expectation that Alexander would pause to consolidate his gains after taking the imperial core, as he had in Egypt. Somewhere on this subreddit, I have a very long answer that goes through the Iranian phase of Alexander's conquest in detail, but I can't find it to link off. Essentially, the Alexandrian sources repeatedly mention that Darius and then Bessus tried to gather a large army from these eastern provinces, but Alexander marched in before they could all gather in one place and was able to fight individual Satraps and local forces individually all the way to Bactria, where Bessus was just handed over to Alexander once it was clear that there simply wasn't an empire to support him any more.

In addition to everything I've discussed about the various resource and preparedness deficiencies, it should also be noted that Alexander only directly conquered and occupied the important parts of the Empire. He secured the western coast in a slow and methodical crawl through all of the major cities, but once he started moving east, it was a question of seizing the centers of power and controlling the administration and large treasuries rather than trying to occupy every city and acre of land. So long as loyalist pockets remained pockets cut off from Darius III's support, they could be suppressed with little effort. The most extreme example of this is eastern Anatolia and the Caucasus. Alexander never dealt with those areas at all, which is why local Persian/Iranian dynasties held power there throughout the Hellenistic Period. So long as they weren't a serious threat to his rear they could be ignored entirely.

There are numerous good discussions on this sub about this and I'll refer you to a couple, but first I'll ramble on summarizing the idea a bit.

There are a few things to keep in mind. First "The" Persian Empire wasn't a cohesive, centralized state practicing complete fealty to a Persian king. To quote u/iphikrates in an answer I'll link in a second, empires of the time, particularly the geographically vast Persian empire, were "patchworks of smaller, semi-autonomous communities". These communities in some cases had been around for thousands of years. There was no way to make, for example, the Babylonians "be" Persians, much less the Greek colonists in Anatolia.

You shouldn't overcorrect and imagine the Persians as figurehead rulers of various states - they appointed satraps, they did intervene in local affairs as needed, and they did put down rebellions. The Persians were king and for a couple of hundred years they held the empire together more or less successfully.

But it was no trivial matter to collect together a great "Persian" army and project force somewhere, even within their own borders (Xerxes for example seems to have done so in his invasion of Greece, though we don't really know how large a force it was and the logistics and planning were years in the making). Still, Darius was able to meet Alexander with large armies several times, but never with the overwhelming force you'd imagine the world's largest empire to be able to muster. He did frequently outnumber Alexander but never decisively.

The other problem for the Persians is that the various satrapies (the Persian method of organization of their territories) weren't necessarily all that loyal to the Persian king. A lot of places were content to let Alexander take over, especially since Alexander often kept the existing organisational structure in place, even the original satraps in some cases. A couple of hundred years earlier Babylon had been the most powerful, largest city in the world. They had great regional importance under the Achaemenids but it was still a demotion of sorts and the prospect of Alexander making them a world capital again must have been enticing. You mentioned Egypt, Egypt proper in fact appears to have surrendered without a fight. This was right after the leader of Gaza had led a fierce resistance (one story has him refusing to accept Alexander and getting dragged behind his chariot, a clear reference to Achilles). Why the satrap of Egypt surrendered is not exactly clear. He may simply had realized it wasn't a winnable situation (Alexander having conquered Phoenicia, Syria, etc by then) and Egypt may simply not have had much love for the Persians. They had only recently been reconquered by them after a period of independence.

What about Alexander's army itself? It was well organized, well trained, experienced (Macedon had conquered/united all of Greece before beginning the Persian campaign), and yes, well-lead. Also, I don't believe Macedon was still a client kingdom of Persia by then. The fact that it had been in the past isn't terribly meaningful I think. Many (most?) of the Greek city states submitted to the Persians during Xerxes' invasion and Macedon was no exception, except that it was a kingdom instead of a city state.

Anyways, that's my rambling done, here are some quality answers for reference!

The answer I quoted above about the political nature of the empire (the question is deleted but you can infer the context):

https://www.reddit.com/r/AskHistorians/comments/e8nkcz/deleted_by_user/

And an answer from u/XenophontheAthenian about Alexander's military prowess. The asker here interestingly takes the opposite stance of you; that Alexander actually deserves less credit for his success because he was inheriting a skilled army and tactics from his father (that Xenophon disagrees with).

https://www.reddit.com/r/AskHistorians/comments/2vbq54/comment/cogeuvi/

Here's another answer from iphikrates about the lead up to the invasion, hopefully illustrating this whole affair wasn't quite as simple as march in and kill everyone in the way: https://www.reddit.com/r/AskHistorians/comments/v1by5o/as_phillip_ii_of_macedon_was_preparing_and/