My 4 planets // 10credits, 2crystals/metal
That's your problem right there. Four planets will not be able to support a competitive late-game force in most cases, and income that low is indicative that you're on the verge of collapse. You need to get a larger empire and grab a bigger share of the map. The huge map has about 80 planets, so even with 8 players that means your fair share is ten planets. That will get you a good mid-sized empire that should be able to crack a starbase by brute force; if you can build up to about 20, that should give you critical mass to just roll over the rest of the solar system.
Should I be making a beeline for my opponent, colonize, and then backfill?
Generally you only want to skip over planets if they have excessive militia. Otherwise, colonizing them along your way is a good idea. Definitely avoid and backfill any "dead end" worlds that are out of your way, but otherwise keep pace and focus on capturing tactical worlds early on.
More important than beelining (which can be critical if you identify a critical choke-point world) is learning how to deal with the militia quickly. It's feasible to move with incredible speed and capture planets in rapid succession; I generally hold to the rule of thumb of one planet every 3 minutes for the first fifteen minutes of the game. One of the keys is to knock out the Krosovs in the militia first, then immediately colonize and build a turret to clean up the remaining militia, enabling your capital ship to move ahead before everything has been defeated. You can save a lot of time this way, and that means more planets under your control to fuel your early war machine.
It should also be possible to defeat one of these unfair opponents before they even get their starbase operational. As Vasari, if you can put a starbase on their homeworld, that can often be enough to knock them out of the game completely since they'll suicide their fleet against it.