What did you see if you go here?
Right Skies! And what have all (except TF2) of them together?
Right MASSIVE CLOUDLAYERS!
They reduce drastically the gradient in your Skybox and they also make your Sky more realistic. So bring in some more Clouds to add variation and always save it on the highest possible setting
. And of course always save a Skybox with "NO MIPMAPS" checked.
You can shit on that Star problem ;) most of the people will never notice it. Add Clouds and maybe a Mountain line in the back and there view will never land on the Stars :P