And if you were to give each of them different phases, would the sound start to sound "off", or would it sound the same? All the same frequencies would be present, which makes me think it might sound exactly the same. But on the other hand, the way they add up would be different, so could there be some cancellation that wouldn't be present when they all had the same phase?
Also, does this same-phase relationship occur as often with non-harmonic overtones/partials as well?
It seems that the harmonic (integer multiple) overtones of a sound usually all have the same phase. Is this true...?
No, I don't think this is generally true, although it may be true for certain instruments. What led you to believe this? In trumpet tones, for example, the different harmonics come up at different times during the attack, so it seems unlikely to me that they're all in phase. But Ross Millikan pointed out in a comment that for a plucked string we do expect all the components to be in phase, in the sense that they all have maxima at the same time that the fundamental has a maximum; this is not the same as all having zero-crossings at the same time that the fundamental does, so there is an ambiguity in what you mean by "same phase."
And if you were to give each of them different phases, would the sound start to sound "off", or would it sound the same?
With a few exceptions in unusual situations, the ear-brain system is deaf to phase. The exceptions involve unusual sounds like cannons firing --- the lore is that one can distinguish the sound of a cannon firing from the same sound with the pressure differences inverted.
The harmonics are a mathematical construct of the Fourier series
You have some complex repeated, unchanging wave form at some single frequency, $f$. That's all you have: one weird wave form, one frequency. No overtones, no harmonocs, nothing...
However, suppose you decide to approximate the weird wave form by combining sine and cosine waves. You decide to try using sine and cosine waves with the same phase as the weird wave form, and with frequencies of $f$, $2f$, $3f$, and so on. (You could always try some other wave form, I'm guessing?)
Fourier says that you can always select amplitudes for these sine and cosine waves such that your approximation gets better and better as you add more and more terms.
So now you can analyze how your weird wave form behaves in any situation by analyzing how each of the sine and cosine waves are affected...
Note also that "shifted phase harmonics" are already mathematically included in the standard Fourier Series:$$A\sin(nf)+B\cos(nf)=\sqrt{(A^2+B^2)}\sin(nF+p)$$ $$\text{where }\tan(p)=\frac{B}{A}$$
