Let's say we're in the key of C. Can one harmonize with one set of chords, and then do the song over and harmonize with a different set of chords and still have the song sound just as good?
Yes. It's quite often doe. Sometimes several sets of chords will fit a melody. Sometimes the melody consists of many non-chord tones so it's easy to change the chords. The song "Mack the Knife" opens with the same melody over different chords. It has something like C-E-A-A (rising) three times with a C-Major, A-minor, and d-minor chords. The C-E is an unaccented pickup and the A acts as a sixth, then root, then fifth, over the underlying harmony. The "heavy" (my term) notes in the melody get nice harmonies, the unaccented stuff need not be consonant (probably as good if dissonant).
Yes! A good example of this is "That's All" by Genesis. Although it's two halves of a verse (not verse and chorus).
These words are over G Em D = first half of a verse
just as I thought I was doing alright thought I was wrong when I thought I was right it's always the same it's just a shame, that's all
The next few lines are over Am7 and D = second half of verse
I can see day, you can see nght You tell me it's black when I know that it's white Always the same, it';s just a shame that's all
.. but the sung tune is the same. It fits over both sets of chords but occupies a different place in their scale.
Here's the whole song: That's All - Genesis
Yes, you are describing reharmonization. A new chordal accompaniment can give the same melody a new sound by simply changing the harmony. Of course, whether or not it sounds better is up to you.
Oh yes indeed. Starting small, you can substitute the relative minor/major for one of the chords, or for a few. This will add a little spice without hijacking the harmony. It's really up to your taste, inventiveness and what the genre will stand.
"Just as good" is a purely subjective assessment, but it is certainly possible, and it has been used for a long time.
It's common in jazz, on a fairly small scale - for example see https://www.justinguitar.com/en/JA-030-1625Subs.php for ten alternatives to a common chord sequence. (The link has a video, as well as written explanations)
In fact, in the 16th and 17th centuries there was a genre of composition where a composer simply took an ascending and descending major scale (in long notes) as the "tune", and demonstrated how many different ways it could be harmonized. Often, these compositions continued for 20 or 30 or more different variations.
It doesn't seem to be very common in modern "pop" music, though.
Yes, but the prevalence of that practice varies.
It was rare in the baroque and classical eras. For an early example see Mozart's violin sonata in E minor, where the recapitulation is harmonized quite differently from the exposition.
In romantic and 20th-century music, a much extended set of harmonic possibilities became common, so reharmonization became more frequent. For instance, Debussy's violoncello sonata begins with characteristic motiv that is repeated nine times throughout the movement, always with a different accompaniment. (This has been compared to an impressionist painter painting the same catheral front again and again, because the light was different each time.)
I think most music lovers would agree that in these cases, the repeated, changed melodies sound at least as good as the original.