Figured out the issue.
Disable/Whitelist your antivirus for AOE3. Specifically in my case it was Malwarebytes.
I was helping my friend with this issue and I didn’t have it myself. Based on the rumors I thought it was a file permission issue so I ran Nirsoft’s Process Activity View on his computer to see what files AOE3 is trying to access. There was a lot of failed options, so I decided to compare that to my own computer trying to load AOE3 (which was known good at the time).
So for the first time I ran into the issue myself and it immediately started loading fast as soon as I stopped Nirsoft from monitor age3de.exe which lead me to believe that the issue was actually Nirsoft inspecting the EXE. Similarly to how an Antivirus would inspect a running exe. So we tested it and disabled Malwarebytes which he has running in realtime mode, and now he loads immediately instead of 5+ minutes. So disable your Antivirus or any other thing that might be monitoring the exe or file system access.