I did not have this problem. I can't exactly go cruel, but I can easily take anything Unfair and below with ease.
Any time I go above Unfair though, it's just insane. I seriously can't seem to find a strategy that works... except build a map big enough that the computer doesn't find you until you've got a formidable defense up... and even then the superior numbers are in the extremes that they overwhelm starbases.
Edit: Turtle strategy works VERY well in diplomacy... at least for Advent. I noticed someone mentioning them using health regen to lessen the impact of meteor swarm. There's a few things to note about star bases, the Advent in particular.
Here are the upgrades you should get in this order for starbases that are defending primary targets of the computer:
6: Meteor Swarm.
7 and 8 can be used however, but it's important that those be purchased in that order. That will wipe out just about any fleet with 1 major exception: A fleet containing 20+ Anti structure frigates. In this case, begin throwing everything you can at those frigates.
Other than that, this will wipe out massive fleets, and allows for effective turtle strategies. If you're not maxing out both hitpoints AND Attack power, and trying to rely solely on the power of meteor swarm, you can kiss your starbase goodbye. You must also max out shield, armor and hitpoints in the tech tree too. I also like to place a pair of regen platforms next to the starbase along with a full complement of hangar defenses. With all the defenses lumped together, it becomes impossible for them to fully deactivate the shield regeneration, and the weapons of the starbase eliminate most of the frigates that try to break away to target them. In short, nothing short of massed anti structure frigates can break it. Even then, it becomes a serious task for the computer to break through. If you're turtling properly, they have to do that at each and every planet they try to conquer... and it becomes massively costly. They'll lose more than 5 times what they destroy.