I keep on telling people I think Jeux d'enfants is one of the best French films I've ever seen. I suppose it could be called a romance, but it doesn't really fit the soppy romcom genre. Wonderful actors too, Marion Cotillard and Guillaume Canet.
This is a very useful thread Paris is a touching film, and Paris, Je T'aime is one of my favourites, a series of short love stories in Paris, very arty lol. (You might be able to tell, I love Paris ^_^)
I would ditto the recommendations of the Three Colours Trilogy, Le Samourai and La Haine. Le Samourai in particular is outstanding.
I would NOT ditto the recommendation of Amelie, which I find so overly sweet to the point of pulling my hair out. I don't care for Breathless either, and would recommend Band of Outsiders or Vivre Sa Vie if you want to check out Godard, but Breathless is definitely a must-see for its importance.
A few more:
The Double Life of Veronique - The same director of the Three Colours trilogy, and the actress of Three Colours: Red. Set in both Poland and France, about a woman who happens across her exact double.
Last Year at Marienbad - One of the best films of all time, and most important of art cinema. If you're to see any film on this list/thread - please don't miss out on this one!
Army of Shadows - A real gripping story of the French resistance, pretty much regarded as the definitive film on the topic. Beautiful and tragic - Same director as Le Samourai.