[PvK]

Why not add a dimension or two? This is space, after all, not a Rogue dungeon limited to up and down. That is, there could be easy regions and harder regions, and you get to choose where to go, with the flavor, risks and rewards varying accordingly? That would provide difficulty while also making sense.

This would also avoid the problem with so many conventional D&D-box-thinking games where the difficulty of the universe surreally warps around the player's strength. (Such games have gaining ability result in also becoming somewhat relatively weaker because most/all things "level up" with the player... for no in-game reason other than balance.)

There are natural ways to keep things interesting without increasing single foe power. For example, you can have consequences of great success. If you are wiping out large swaths of foes, there might be some consequences such as:
* They raise an alarm and after some time, more and stronger reaction forces will show up.
* They raise an alarm and start evacuating pulling out their own targets and loot from out of your way.
* They try to negotiate peace terms.
* If you are doing them grievous merciless harm, they may send a complaint and/or aid request to some stronger power that may arrive to protect them, or to try to extract retribution later.
* Another stronger group might take notice and intercede of their own accord.