Some more that haven’t been mentioned (these are all fairly recent pop singers):
Mylene Farmer
Indochine
Jil Caplan
France Gall (her career went from the 60s to the 80s)
Ed
Ange - Dramatic, theatrical prog-rock, similar to Peter Gabriel-era Genesis but more intense. Also strongly influenced by Jacques Brel. Recommended to start with: Au Dela du Delire.
Malicorne - Adaptations of old French folk songs; sort of a French Steeleye Span. See also the solo work of the band’s leader, Gabriel Yacoub. Recommended to start with: any of the three self-titled albums (especially the blue one).
I like Les Negresses Vertes, who I would describe as “somewhat Gypsy Kings-ish.”
suranyi, I’m a fan of Mylène Farmer, too. My roommate used to request “Desenchantée” whenever we went clubbing together.
I usually describe her as a fusion of Madonna and Bjork.
“Madonna and Bjork”. That’s pretty good!
Ed
I’m surprised no one has mentioned Patrick Bruel yet. Check out his album “Entre-duex”, it’s VERY French music from the 30’s and 40’s (although he’s modern).
Another favorite of mine not yet mentioned is Charles Aznavour. Anything by him is really terrific.
Second me on loving Les Nubians–I’ve got one of their CD’s playing on Rhapsody almost constantly.
There’s another CD I found in the used CD section, called Reve Orange. I’m not sure offhand who it’s by, but I really enjoy it.
The French (rough) equivalent to Buddy Holly or Chuck Berry was Johnny Halliday, the first big French rock-'n-roll star, whose heyday was the early-mid '60’s. I’ve never heard any of his stuff so I can’t vouch for it.
FWIW, Halliday has a dishy celeb nephew: the actor Michael Vartan (Never Been Kissed; TV’s Alias). 
I highly recommend Carla Bruni. Her music is great and her lyrics are both poetical and very clear, clear enough to translate directly to English even while she is singing. Check out her songs before you learn anything about her, so as not to risk any prejudice
she does happen to be a model, but she’s no Naomi Campbell. She has real talent