In my current game the world is in an Era of Egoism, and I just made contact with another major. A dozen or spies later, and I am able to see that, at the least, every single OHQ commander in their empire has 0 relations, plus their SHQ. Which is....yeah. Meanwhile in my empire, i'm at the peak of the Era and have most leaders still over 80.
If we assume that the rest of their Leaders are like that, it means that if I went to war with this AI, they'd be heavily inferior to me in production, research, combat skill, etc. Even if we both had equal resources. Not to mention that they must be having a mountain of negative events and then failing a lot of the rolls due to the malus you get for having bad relations.
I haven't seen any rebels to far, so hopefully AI is at least spared that. I'm playing on Regular, don't know if AI get better at handling leader relations on higher difficulties. But they clearly can't cope on Regular.