Ile de la Cite, with Notre Dame, Saint Chapelle and possibly the Conciergerie.
You're going to want to see the Eiffel Tower. I cordially detest the Eiffel Tower. Hey, if you go up to Sacre Coeur to watch the sunset you can see it from there! (you have to edge round to the right a bit. At night it goes all sparkly on the hour). Restaurants are pretty touristy in Montmartre- best stick to a couple of drinks up there and descend to eat.
I'm equally unbothered about the Arc de Triomphe and the Champs Elysees.
Not unmissable, but a Very Good Thing to Do: an extended wander around the Left Bank taking in some of the following: Jardin des Plantes, Grand Mosquee de Paris (gorgeous women only hamam!*), Place de Contrescarpe and Rue Mouffetard, the Pantheon and St Genevieve, Arenes de Lutece, St Severin, the Latin Quarter, Shakespeare & Co.
Ditto: a wander up/ down the Canal St Martin.
*a gorgeous hamam for women, not technically a hamam for gorgeous women, but when I went pretty much every other woman was gorgeous, because....Paris.