You might have only been to higher-end restaurants, and not the "good ol' french" types that are as much about the atmosphere as they are about the food. The kind of thing I could only name as "à la bonne franquette".
For a representative sample of the kind of place I'm talking about, try 'Chez Gladines' in the 13th arrondissement.