The Level Scaling always annoyed me in SPG2, but here it seems to fit.

You start with a Gunboat and fights are rather tough but doable. No way you can invade a station or a planet. But you can do Search and Destroy missions to improve in level or gather credits. - feels good

You get your first Destroyer and the first few missions are a piece of cake, you feel strong. - feels good

Soon every single encounter has also Destroyers and you are forced to get some bigger ship again.
Then every single encounter has bigger ships as well. - feels bad

In my game at the moment all encounters are Carriers, Dreadnoughts and Cruisers with a few Destroyer in their fleet. I have a Dreadnought, Carrier, Battleship and a few Cruisers in my fleet just to do basic stuff. - feels bad

There are a few random enemy fleets with only Cruisers, Destroyers and even some Frigate, Corvette down to Gunboats but they are rare. - feels good

Sometimes I have to siege a facility before I can take it. Going in, kill a few, retreat, going in, kill a few, retreat and then the final assault. - feels good

Just suggestion:
- have a more spread level in the Job Board like your level -20 up to your level i.e. you are level 35 then you see missions 15 - 35

Yeah, we have some more blanacing to do to turn these "feels bad" to "feels good". :)