Do you usually say "the sky is partially cloudy" or "the sky is partly cloudy"? Are they both correct? Is there any difference between "partly and partially" in the last sentence? Is there any difference between "partly" and "partially" in general? They both sound natural to me.
in some degree
pertaining to a part
The bottom line is partly cloudy is an idiomatic phrase. Whatever its drawbacks, it's been in use for quite a while and does roll off the tongue quite naturally.
Partly cloudy means that the sky has some cloudy parts and some not cloudy parts.
Partially clouded over means that after starting out clear, there was a transition and the blue sky has been gradually, but not completely, obscured by developing (or entering) clouds.