Tonight we accidently went to the Djerba, a Tunisian restaurant. Nice place, nice staff, nice food, very reasonnably priced (52EUR for our 2 couscous, a bottle of wine, dessert and tea). To top it all off, the whole place was smoke-free the entire night. Only downside is, it's not actually non-smoking: we were just lucky.
EDIT: The interesting thing about the smoke is that there were smokers, but they went outside. Strange things are happening in France, let me tell you.
Le Djerba: Place Esquirol Impasse St Géraud, 05 61 21 80 12