I've edited the original post with an updated project description just in case anyone is interested.
Thanks for the tips Doom_user! I will be sure to do as many of those things that I can (some will be impossible now due to static limitations...ugh).
5 reccommendations for COOP friendly levels
Thanks 40oz, I'm glad you like the skies :).
do you make them yourself? If so, could you share some tips?
I've spent way too many hours trying to figure out the best way to make sky textures. I've tried making them from scratch but that's pretty difficult to do if you want to make them look somewhat natural. I've also tried using stock photos which helps to retain a more natural look, but I've found that you have to be very selective in the kind of photos you use. So I've settled on a method that basically uses stock photos as a base which I heavily modify so that it will look good in Doom's palette. If your trying to make a sky from scratch, then my tips might not be quite as useful.
It depends on the texture your looking for, but I've found that most sky textures need lots of details. Unlike normal textures, the player always views the sky texture as if its zoomed in. Because of this, large swaths of blotchy colors don't look nearly as good in the sky versus what you see in the image editor. Take the old MAP02 sky for example. I was attempting to make a low contrast, soft sky texture. But Doom's color palette just can't pull off that look very well. In the new sky for MAP02, you can see that the smaller, more densely packed cloud texture, along with more contrast, works waaaay better. Most of the time the base image I'm using won't have enough details, so I will either paint some new ones in or play around with the clone tool a bit.
Contrast is really important too. The way I approach coloring is to desaturate my base texture, fiddle around with contrast/brightness a bit, and then experiment with various color palettes. Different ranges in the Doom palette work better at different contrasts and brightnesses. But for the most part, the higher the contrast, the easier it is for a color range to bite into the image without losing details. Colors like the blue range work best in a high-contrast image. You can get away with slightly less contrast with the browns and pinks since those ranges have more colors and can work well with a few other ranges. Many times I'll have to do some manual painting to get the shadows and highlights just right since fiddling with the brightness/contrast sliders can kill off a lot of your details.
The addition of a horizon is actually something I just discovered recently. It goes a long way in making a sky texture look convincing. I don't think its a necessity though since Doom's original sky textures (well, some of them) don't have vanishing points and they still look great. But if its something you can pull off, it does add a nice layer of depth. Most of my latest skies have the horizon built in from the stock photos I've used. Though I did have some success with using a perspective manipulation tool in GIMP to create a horizon line. If your creating one from scratch, the perspective tool might work though you'll have to try and paint/clone the lower corners where that line gets shrunk.
Something else you may want to experiment with is creating custom color swatches. Maybe GIMP lacks good color palette tools, but I had to rip out each color range from the Doom palette myself and save them as separate color palettes for easy usage. Though you don't always want a sky texture that uses just one color range. So I started making custom color palettes by picking colors from Doom's palette. Some color ranges work pretty well together. For example, the E4 sky uses an orange and pink palette and it looks really awesome. I'm using an extended version of that same color range in the MAP04 sky texture that you can see above. If you can't make a custom color range that works well, sometimes you can get away with painting over top a paletted image (in RGB mode) using colors from the palette and they will still mesh together with a bit of detail lose after converting back to index mode. The desaturated browns and greens can work well for this, and they sometimes play nice with the brown and green range too.
As far as creating a sky from scratch, I think what I would probably do is look at stock photos of skies and just experiment with various methods of noise creation and layer mixing to try and replicate a natural looking sky. The last time I seriously tried it, I had problems creating enough detail. Also getting the perspective right is tricky too since I would usually end up making something that felt really stilted and/or overbearing. If you don't mind working with stock photos, you can mix custom made stuff with that and create something that is entirely different looking. I did that with MAP05's and MAP06's skies.
Hopefully all of that is helpful in some way :). I still struggle with sky texture creation after having remade the skies for this project atleast 9 or 10 times now. Although I guess all of the retakes and repetition helped me figure out the better methods.