The problem is when you are playing against the AI it can field bigger fleets faster than you can. Your advantage is you can field better fleets. What hurts isn't just the fact that you can't get out capitals but you can't get out Starbases. Even if you get out Starbases and caps you can't equip them with items to allow them to do the damage necessary to keep up with defensive upgrades.
Bumping the refineries up a tier might not be too bad on its own. Reducing survey reliability might not be too bad on its own. Randomizing surveys might not be too bad. Combining all three is terrible.
I don't know how others play but I play with a mix of Caps, Frigates, and the Titan. In my opinion, this did not need to be fixed. This patch seems to be aimed at PVP players at the expense of PVE players. At best it draws out the early game, which isn't needed. Where the game needs help is in the end game when the player achieves "checkmate" and the only thing keeping the game going is the need to capture home planets or enough planets. At worst this patch makes it much more difficult to get past the early game as the AI rushes with large fleets that the player can't stop because they can't build the defenses, build a comparable fleet, and can't upgrade their fleet to keep up. While I am sure that higher-level players are going to adapt and manage to do fine (although probably with some cheesy strategy), I suspect it is going to drive more average-level players away from the game.
