Avignon is very scenic and from there you can visit Nimes, Arles, St Remy de Provence, les Baux des Provences. Also if you enjoy hilltop villages you could visit Gordes and Roussillon both of which are very interesting.
We found Rouen very interesting , very medieval and historic and we had a couple of good meals there.

Strasbourg is also interesting and very attractive but as someone else has said not quite as French as Avignon.

Someone recommended Rocamadour area and I would second that - also the Gouffre de Padirac. The whole area is interesting and scenic.