EDIT: I think the mistake a lot of people make is building Starships too early in the game. Starships are powerful but they don't bring a lot of bang/buck. I used to do that too. Starships also use a lot of energy so you will run out of that too. As you can see here.
I love Starships and usually run quite a heavy Starship fleet, at least in the mid game.
However, the only starships I build early are the Flagships and that is for the Attack Boost they give my fleet, the other starships have to wait until I have a few systems under control so I can afford to build them without cratering my economy. (Either resources or energy economy can crash easily on starships.)
On the actual topic of the thread, I'm not sure.
Starships were re-worked to give them the 'survivability' trait to make them nice when under player control.
That means that the AI gets the same 'survivability' when starships are under it's control.
Having said that, this survivability is perhaps magnified too much when you get a high mark starship to the face in the early game for whatever reason as you don't have the fleet to kill it quickly.
The two big culprits for this are threat and raid engines. What about adding two more rules to map generation?
- No Mk IV worlds adjacent to a human homeworld
- No Raid Engine within 2 hops of a human homeworld (so 3 hops the closest a raid engine could be).
This would allow a player to be guaranteed the ability to capture at least one more planet (probably 2 or 3 on most maps) before they ran into a mechanic that made them face a Mk IV or V starship. (I don't consider a Mk III starship OP enough to be a problem against the fleet a single human world can support.)