Thanks for the suggestions, folks, keep 'em coming!
And Peter, thanks for reminding me about the songs with intervals. I know I have a list of those somewhere. The ones I remember off the top of my head are (these are ascending intervals, I think there are different songs for descending intervals):
Minor 3rd: "Greensleeves"
Major 3rd: "Oh When the Saints"
Perfect 4th: "Here Comes the Bride"
Augmented 4th: "Maria"
Perfect 5th: "Twinkle Twinkle"
Minor 6th: "Go Down, Moses"
Major 6th: "My Bonnie"
Octave: "Somewhere Over the Rainbow"