Carmina Burana, Orff. The lyrics are in Latin. I took a couple years of Latin in undergrad, so it's fun to chant along.
Anything by Ali Farka Toure. He sings in Malinese and plays a fusion of traditional Malinese music and Delta Blues. Really. It sounds familiar and totally exotic at the same time. I can't recommend him enough.
Various Stereolab recordings. They switch up between French and English. Always fun.
Speaking of France, try some Édith Piaf.
And hasn't Celine Dion recorded in French, as well?

Also, the Super Furry Animals occasionally cut loose in Welsh (making them even weirder, but I love those guys) and try some Mexican banda and corridos.