I'd start with Bodoni and explore the whole didone category.

Do look at all the fonts here:
http://typofonderie.com/
Most of them are too mainstream in this case, but there's some nice quirky stuff too.

hhp

Paris, France?

I’d start with Bodoni and explore the whole didone category.

I think starting with Bodoni is fine. I would not finish with Bodoni, though. Using a didone face in order to achieve that air de Paris ambiance feels a bit too obvious. What about trying one of those rarely-used Frutiger serif designs?

Bodoni is Italian; it would be a bad choice for Paris.
In addition both Bodoni and Didot are neolassical fonts used all over Europe starting from the end of 17th Century.

You'll maybe find some nice inspirations in this video
http://vimeo.com/channels/nicetype/18886355