Making a high quality cubemap/sky?

If you just want six textures:
You could turn off compression.
You could use one grayscale alpha texture (which may compress better) and a separate colorization texture.
You could use a custom shader that measures brightness and then calculates color, to avoid compression problems.

However, I’ve also seen artists have very good success with sky boxes that are made of geometry – separate polygons for various “objects” in the sky. This lets you use more, smaller textures for a visually higher-resolution result.