Wow, it really depends the style you're searching for. Here is a proposition in different styles :
* Classic "oldies" :
- Georges Brassens "L'auvergnat", "Les copains d'abord"
- Jacques Brel "Amsterdam", "Le plat pays", "Bruxelles"
- Edith Piaf "La foule", "Hymne à l'amour"
- Barbara "L'aigle noir", "Gottingen"
- Charles Aznavour "La mamma"
- Serge Gainsbourg "La javanaise", "Elisa", "Melody Nelson", "Je t'aime, moi non plus", "Love on the beat" and so many songs... (very different styles in his career)
* 70's/80's singers
- Renaud "Mistral gagnant", "Laisse béton", "Gérard Lambert"
- Jean-Jacques Goldman "La vie par procuration", "Envole moi"
- Michel Berger "Paradis blanc"
- Nino Ferrer "Le sud"
Pop/rock
- Daniel Darc "La pluie qui tombe" (2003 or 2004)
- Téléphone (80's band) "Ca c'est vraiment toi", "Flipper", "Un autre monde", "Métro c'est trop"
- Louis Bertignac "Ces idées là"
- Jean-Louis Aubert "Juste une illusion", "Les plages"
- Noir Désir (the biggest French rock band) "Tostaky", "Un jour en France", "En route pour la joie", "Le vent nous portera"
- Alain Bashung "Madame rêve", "Gaby", "Osez Joséphine", "La nuit je mens"
- Indochine "J'ai demandé à la lune", "L'aventurier", "Le grand secret"
- Louise Attaque "Les nuits parisiennes", "Si c'était hier", "La plume"
- Mano Negra "Pas assez de toi" and many songs in Spanish :)
- Manu Chao "Me gustas tu" (again in Spanish)
- Mylène Farmer "Regrets", "Sans contrefaçon", "XXL", "Désenchantée"
- Najoua Belyzel "Gabriel"
- Fatals Picards "L'amour à la française" (a song everybody can understand even if they don't know French well :) )
- Bratisla Boys "Stach stach" (a very silly song, supposedly in Bratislavanish :) )
* Hard/heavy/punk
- Trust "Antisocial" (THE French hard/heavy metal anthem)
- Metal Urbain "Panik", "Hello hello", "J'irai chier dans ton vomi"
* Goth music
- Collection d'Arnell Andrea (hard to recommand one song)
* Modern french "chanson"
- Camille "Ta douleur", "Pour que l'amour me quitte"
- Anais "Mon coeur, mon amour"
- Olivia Ruiz "J'traine les pieds", "Non dits"
- Weepers circus "La renarde" (nice ballad)
- Miossec "Non non non non"
- Dominique A "L'horizon"
- Carla Bruni (yes, she has French nationality) "Quelqu'un m'a dit"
* Rap/slam
- Grand Corps Malade "Les voyages en train"
- Abd Al Malik "12 septembre 2001", "Les autres"
* R'n'b/hip hop/rap
- Nadiya "Tous ces mots"
- Diam's "La boulette"
- I AM and Supreme NTM (don't know much these bands, but they are the references in French rap)
- Amel Bent "Ma philosophie"
- MC Solaar "Nouveau western"
* Other
- Yann Tiersen ("Amélie" movie soundtrack)
- Alan Stivell "Tri martolod" (adaptation from a Breton traditionnal song)
- I Muvrini "Curagiu" (in Corsican)
- Air, Charlotte Gainsbourg... but they sing in English.
Here is all the list I can make in 20 Min. Give a more precise style next time, I didn't include many recent songs, in fact.