sunday is a real problem. reservations are very difficult because so few are open. i go through zagat ("S" in a black block) and Michelin red guide. if you are staying at an upper end hotel, the concierge will know who is open. i also sort of the feeling that some restaurants hold reservations for concierges. most hotels restaurants are open on sunday.
a lot are also closed sat night.
there are a lot of "great" in paris, and price varies greatly. what price range?