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.