I just saw the responses to this thread now since I was cut off from the Internet shortly after I posted it. Paris is amazing and I did stumble upon one tobacco shop which I made my wife take some pictures of. I will hound her to give them to me so I can post them.
Paris is an amazingly beautiful city. The hotel we stayed in (which is where I took the first shot from) was in a very old building It was nice, but there weren't many luxuries in the hotel. The elevator that took us to our 5th floor room was incredibly tiny. It held one person and a bag (barely) and that was it. The elevator we have in our house is small but it is at least twice the size of the elevator in the hotel, which my kids found amusing. Parisians are used to cramp quarters compared to North Americans, that's for sure.
I had not been to France since the 1990s and will definitely be going back, though probably to places other than Paris. We are thinking we might go back next summer. So I thought I would ask the question: where have you been to in France and what places (cities, regions etc.) would you recommend?