About the sky, not everything needs to be the same level of detail in a picture. This often is not a very good idea (tho it can work). Thing is that too many details will distract from what you want to show. Hm. The bottom one does not quite work (too noisy, fuzzy I think) and the shadow would have to be fainter and not directly underneath him, but getting cast infront of him.
If I can find some time I might make an edit.
Keep experimenting with those colours, If it is possible with the palette you should try to give the closer things a bit more colour identity. As in not totally cyan sand and such.