I don't know what tech you have, but a bit of planet improvement (Get them all to about 5 or so) helps a LOT. Your population growth rate basically doubles. (Mine went from +0.5 to +1.0. +1.5 after I researched the pop techs.)
It does not take that much to take the Andors down, that 4.3 B power seems to act more like .43 B when it comes to them. A bit of prep work rather then right out attack, and you could take that world a lot quicker then just a flat out attack.
As for how to fix it, I think there is a fairly easy way, less then Chemical put out.
First of all, start all races space faring. The Alliances with each other sounds like a good idea too.
Give each race (save your own) a lot of starting population and Armadas, and a I mean a lot. They should start in the 30s range for Armadas and the low billions on population.
Make each race see your Armadas well they are at your 'home' world, appear to be worth the same as 20(or maybe more) of theirs until you take your first planet. This is to make certain that the entire galaxy does not attack you right away until you take over another world.
Perfect ingame justification. They know how powerful Hydra ships are. They think your fleets really are that strong until they see them in action against a world. The Spy probes reports the results to everyone when you take the first world, so they know that they were greatly overestimating you.
What this means is, you have a lot of work to do, either blowing up massive fleets (add some sort of counter attack option maybe?) Or getting sides to hate each other and fight each other. Then you can walk in and clean up.
Add in a 'Boss' at each world that appears in each fight (and something that disables them, be it mission, building or tech) and it will take time to get anywhere in a Betrayal mode.
It certainly changes the pacing of Betrayal mode, but in the end, I think it would feel like a real Betrayal mode. Your not knocking down people that just started to get to space. Rather you walking in after they are already built up, and removing them.
The end result of this, means when you take your first planet. You better be ready, because the rest of the races will realize what you are up to, and exactly how strong you are when you do.
EDIT:
Well the new version sneaked out well I was typing this. Even more mild then I suggested, but it is starting to move that way. I give the changes a play later and see how they do.