So is it absolutely essential that prepositional phrases come first? I seem to recall someone saying that there are more natural places to put them depending on the sentence, but it's not set in stone.
"var" sentences are not flexible. We would never say "Yıldızlar gökyüzünde var". This emphasizes the location. But to indicate location, we wouldn't use "var". We would just say "Yıldızlar gökyüzünde" (The stars are in the sky)
I guess, the last "ü" was a possessive suffix in the former noun compound "gök yüzü" (literally "heaven face"). With time, the noun compound became a simple noun, but the buffer "n" is still used when other suffixes are added.