The following sites contain full skybox textures available for download.
www.3delyvisions.com/skf1.htm - 17 skybox sets, blue sky's, mountains, grasslands, sunsets.
http://amethyst7.gotdoofed.com/env.htm - 40 skybox sets, textures for many settings, good variety. Don't let the single side preview pic fool you, these are full sets.
http://www.planetside.co.uk/terragen - I thought that mentioning this would be worthy of note, since "TerraGen" was the software used to make most of these skybox textures. Just in case you needed/wanted to make your own someday.
If I find any other sites hosting similar resources I will add the links here. If you are aware of any other sites that might be containing some exquisite skybox sets please post here so that I can update the information accordingly.
Does anyone know a website that might be hosting some free skybox textures, that I could use in the BGE?