I've basically figured out what the problem is.
It's primarily 2 issues. The issue we've covered already, regarding simply unfortunate map placement. The AI often has nowhere to expand to and by the time it can it's taken by someone else.
In regards to the second issue, I'll direct you to the Krynn, everyones favorite monster AI. Why? Morale. The AI is currently experiencing issues managing morale. A bug with the promethion pleasure park (it was giving 6 wealth instead of 6 morale) was compounding this problem. Even fixing that mixup, the AI still struggles with morale.
To test this, I made a mod that gave the AI a +4 bonus to morale on challenging difficulty, this is the first difficulty level where the AI gets bonus'. The difference? Enormous. The entire dynamic of the age of exploration changes. You are probably intimately familiar with the AI sending constructors across the galaxy to steal your resources. This behavior stops. Why? The AI was doing this because it wasn't willing to colonize further due to morale issues. Now with a +4 bonus the AI's morale problems are more reasonably managed and they spam colonizers.
There is a mod floating around in the mod section from someone who made a similar change which boosted AI morale. Until SD works out AI morale management, that is going to be the best fix.
Trust me it makes an enormous difference and the morale boost isn't completely crazy. Most players I am sure are rushing that +4 bonus in the second tier of research as it is for that enormous leg up.