How different would a musical piece sound in different atmospheres? I assume that sound travels differently in other planets depending on what their atmosphere is made of, affecting the frequencies. Is that assumption correct?
It depends on a lot of things. In rough order of weirdness:
As mentioned in the question comments, music played live by stringed and percussive instruments would have the same pitches / timbres. But live music by unmodified wind instruments would have wrong pitches because their pitches are determined by the speed of sound in the "wind". Recorded music played by speakers would not be pitch shifted because speakers just reproduce whatever frequencies are played through them.
If the atmosphere is different enough it could have a different acoustic impedance and instruments and speakers could end up sounding quieter or louder because they are able to transfer their vibrations to the atmosphere less or more efficiently.
The atmosphere may also have different acoustic absorption properties than air. This could act like a frequency filter, cutting out high or low frequencies.
If the atmosphere is different enough it could have a non-trivial acoustic dispersion, where different frequencies travel at different speeds through the medium. I'm not sure what effect this would have on the sound you hear.
That's all I can think of for now.