Consider thinking about the skybox not as one single entity, but several separate entities together creating one impression.
Like different sprites, clean pixeling on simple billbox, orchestrated around, facing the player; overlaps, layers, experiment.
Especially for a space scenario this can work fairly well, even together with some code automatically placing sprites around.