Ich finde eigentlich auch, dass ihr euch die Côte weitgehend sparen könnt. Provence oder Languedoc Roussillon sind wesentlich schöner. In der Provence finde ich von den Städten Arles, Aix-en-Provence und Avignon besonders sehenswert. Sehr hübsch ist auch die alte Stadt Aigues-Mortes, die im Mittelalter, als die Kreuzritter von dort zum Kreuzzug aufbrachen, noch am Meer lag.
Montpellier wurde ja schon ein paar Mal genannt; das ist eine sehr lebendige und schöne Stadt. Aber auch Béziers, Narbonne oder Perpignan haben ihren Reiz. Von den Strandorten ist Collioure mein Lieblingsort.

Von den Städten der Provence würde ich dir unbedingt auch noch Aix-en-Provence, Avignon und Orange empfehlen. Aix-en-Provence besitzt wunderschöne alte Herrenhäuser, eine herrliche Kathedrale mit einem Kreuzgang, einige schöne Märkte und es ist durch die vielen Studenten, die dort leben, auch eine sehr lebendige Stadt.
In Avignon lohnt natürlich das Palais des Papes, der Papstpalast einen Besuch. Einen wunderbaren Blick auf die Stadt hat man von Villeneuve-lès-Avignon am gegenüberliegenden Ufer der Rhône.
In Orange sind die römischen Relikte interessant; das Theater, in dem sogar die Szenenwand erhalten ist, ist wirklich einmalig.
Ansonsten stimme ich einigen vorhergehenden Antworten voll zu; das Languedoc-Roussillon ist unbedingt einen Besuch wert. Die Côte d'Azur dagegen meiner Ansicht nach eher nicht.

Saint-Paul-de-Vence und Vence, ein kleines Stückchen im Hinterland der Küste gelegen, lohnen unbedingt einen Besuch. Ganz in der Nähe ist auch die Fondation Maeght, ein Museum zeitgenössischer Kunst, das auch einen beeindruckenden und herrlich gelegenen Skulpturengarten bietet.
In Cagnes-sur-Mer, dicht bei Nizza gelegen, verbrachte der Maler Renoir seine letzten Lebensjahre. Heute ist in seiner Villa ein Museum untergebracht.

Dumas' Graf von Monte Christo verbrachte viele Jahre Kerkerhaft im Château d'If auf einem Inselchen, das Marseille vorgelagert ist.
Auf einem anderen der provenzalischen Küste vorgelagerten Inselchen, Sainte Marguerite, war der Mann mit der eisernen Maske gefangen, der wirklich existierte (eventuell ein Zwillingsbruder Ludwigs XIV.), der aber auch in vielen Romanen, Theaterstücken und Filmen auftaucht.
Und noch ein dritter Schauplatz in der Provence fällt mir ein: die Kirche in Saintes-Maries-de-la-Mer. Frédéric Mistrals Heldin Mireille (aus dem gleichnamigen Versepos) stirbt dort vor dem Altar.

Ich finde Aix-en-Provence auch schön, würde es aber nicht gerade als Städtchen, sondern bei fast 150 000 Einwohnern schon eher als Stadt bezeichnen.
Ich mag Arles sehr gern, dass sich sowohl eindrucksvoller Relikte aus der Römerzeit (Arena, Theater, Alyscamps) als auch einer wunderschönen romanischen Kirche mit Kreuzgang (Saint-Trophime) rühmen kann. Dazu kommt die Lage an der hier schon recht mächtigen Rhône.
Ein weiterer Favorit von mir ist das am Rande der Camargue gelegene Aigues-Mortes, das noch heute rundum von einer Stadtmauer umgeben ist.

Zu den bereits von hibiskus genannten Gerichten käme in der Gegend von Nizza noch die pissaladière, die provenzalische Version der Pizza.
Die salade nicoise kennt ihr vermutlich schon aus deutschen Restaurants, aber in der Provence gibt es darüber hinaus noch das pan bagnat (wörtlich gebadetes Brot). Das ist ein meist rundes Weißbrot, das mit salade nicoise gefüllt wird. Wenn die Vinaigrette dann das Brot durchdringt, ist das eine absolute Köstlichkeit. Allerdings besteht auch höchste Kleckergefahr! ;)

Genau genommen liegen all die genannten Orte am Rande der Camargue, aber Aigues-Mortes mit der rundum erhaltenen Stadtmauer und der Tour de Constance, in der einst Katharer gefangen gehalten wurden, ist sehr lohnend. Arles ist vielleicht für Fans der Römerzeit noch interessanter als für Mittelalter-Fans, doch Saint-Trophime mit seinem wunderschönen Portal und dem ebenso schönen Kreuzgang sind bedeutende mittelalterliche Bauwerke.
Hier noch mein zusätzlicher Vorschlag: die nahe Arles gelegene Abtei von Montmajour. Sie ist zwar zum Teil Ruine, aber trotzdem sehr beeindruckend und herrlich über der Ebene der Grau gelegen.
Ebenfalls mittelalterlich ist die Wehrkirche in Saintes-Maries-de-la-Mer (dem einzigen Ort, der wohl wirklich in der Camargue liegt), aber der ganze Ort ist sehr überlaufen und fest in der Hand von Touristenmassen, sodass ich dir davon eher abraten würde.

Falls du auch an Antiquitäten-/Trödelmärkten interessiert bist, kann ich dir einen sonntäglichen Besuch in Isle-sur-la-Sorgue, etwa 25 km östlich von Avignon, empfehlen. Der Markt dort gilt als einer der größten Europas.
Was die allgemeinen Märkte angeht, schließe ich mich Dusautoir an: Aix-en-Provence hat wunderschöne Märkte, auf denen du die Provence wirklich mit allen Sinnen genießen kannst.

Die obere Corniche, die an der Côte d'Azur hoch über dem Meer entlangführt, ist auch ausgesprochen reizvoll.

Ich würde dir raten, dich einige Tage vom Rummel an der Küste zu entfernen und ins Hinterland zu fahren. Natürlich gibt es auch dort Touristen, aber einige Orte wie beispielsweise Saint-Paul-de-Vence oder Vence sind ganz bestimmt einen Besuch wert. Oder mache einen kleinen Abstecher in die Provence: Arles, Avignon, Les Baux, Saint-Rémy, Aix-en-Provence, Aigues-Mortes (am Rand der Camargue) - ich komme ins Träumen, wenn ich nur die Namen aufzähle.

Die drei Städte lassen sich nicht miteinander vergleichen.
Montpellier ist eine alte Stadt, schon seit vielen Jahrhunderten eine bedeutende Universitätsstadt und die Uni bzw. die Studenten prägen auch heute noch zum Teil das Stadtbild.
In Nizza spürt man die lange italienische Vergangenheit noch - selbst im Kulinarischen, die Spezialität pissaladière ist eigentlich nur eine Abart von Pizza. Außerdem merkt man in Nizza, dass es Hafenstadt war und ist.
Antibes ist bedeutend kleiner als die beiden anderen genannten Städte. Es ist eine Kleinstadt mit einem burgähnlichen Schloss, in dem es eine Picasso-Ausstellung gibt, und einer Stadtbefestigung, auf der man einen weiten Teil der Stadt umwandern kann.
Reizvoll sind alle drei Städte.

Ich mag auch noch eine Sehenswürdigkeit am anderen Ufer der Rhône sehr gern, die Chartreuse in Villeneuve-lès-Avignon. Es ist ein weitläufiger Klosterkomplex mit mehreren Kreuzgängen, ein friedlicher stiller Ort. Heute ist die Chartreuse Kulturzentrum, in dem Veranstaltungen stattfinden, manche der Mönchszellen werden auch Künstlern als Unterkunft überlassen.
Und wenn man in Villeneuve-lès-Avignon ist, kann man auch gleich noch das Fort Saint-André ansehen. Von dort aus hat man auch einen fantastischen Blick auf Avignon mit dem Palais des Papes.

Ein wunderschönes Ziel zur Zeit der Lavendelblüte ist auch die Abbaye de Sénanque, weil sich dort Kunst und Natur so wunderbar vereinen. Nicht umsonst sieht man das Bild des blühenden Lavendels vor der romanischen Kirche auf sehr vielen Provence-Büchern.

L'Isle-sur-la-Sorgue, 30 km östlich von Avignon gelegen, ist für seine Antiquitätenmessen bekannt, die vor allem auch im Juli und August stattfinden. Im Französischen ist ehrlicherweise von "antiquités" und "brocantes" (= Trödel) die Rede. Aber wer sich ein bisschen auskennt, kann sicher in der bunten Mischung auch das eine oder andere lohnende Stück entdecken.

Da kann ich dir die Provence und die Côte d'Azur empfehlen. Deren fantastisches Licht hat viele Künstler angezogen. In Aix-en-Provence war Paul Cézanne zu Hause und dort kann man auch sein Atelier besichtigen. Van Gogh lebte in Arles und dann im nahe gelegenen Kloster (damals Nervenheilanstalt) von Saint-Paul-de-Mausole (bei Saint-Rémy). In Arles erinnert nicht sehr viel an ihn, in Saint-Paul kann man sein Zimmer sehen. Jean Cocteau hat viel an der Côte d'Azur gemalt - in Villefranche steht eine von ihm ausgemalte Kapelle, in Menton hat er den Hochzeitssaal des Rathauses ausgemalt. Auf den Spuren Picassos kann man in Antibes (Schloss) und in Vallauris wandeln. Sein letzter Wohnsitz, das Schloss Vauvenargues, ist nicht für die Öffentlichkeit zugänglich. In Cagnes-sur-Mer bei Nizza ist im Haus Renoirs ein Museum untergebracht. Matisse hat in Vence eine Kapelle ausgemalt.
Und wahrscheinlich gibt es noch viele andere, die mir jetzt gar nicht eingefallen sind.

Ich stimme den anderen Antworten voll und ganz zu: Avignon ist in jedem Fall eine Reise wert - die Brücke, der Pont Saint-Bénézet, ist sicherlich nicht der wesentliche Grund dafür. Einen sehr schönen Blick auf die Brücke hast du vom Rocher des Doms mit seiner Parkanlage oberhalb des Papstpalastes. Wer nicht zu Fuß hochgehen will, kann mit dem kleinen touristischen Bähnchen, das vor dem Papstpalast abfährt, hochfahren.

Absolut sehenswert sind die Ausgrabungsstätten und das Museum in Vaison-la-Romaine. Der Beiname ("la Romaine" = "die Römische") ist wirklich zutreffend. Dort ist die größte Ausgrabungsstätte von ganz Frankreich. Es gibt Reste von Häusern ebenso zu sehen wie von Tempeln, dazu ein relativ gut erhaltenes römisches Theater. Das Museum zeigt wunderschöne vor Ort gefundene Mosaiken, dazu Artefakte wie Öllampen, Gläser, Münzen und Ähnliches. Über die Ouvèze führt eine Römerbrücke, die selbst dem reißenden Hochwasser 1992 standgehalten hat.

Ich habe eigentlich meine schönsten Provence-Urlaube im Frühjahr gehabt. Es stimmt natürlich, die Lavendelblüte entgeht einem dann, aber es ist herrlich, aus dem oft Anfang April noch ziemlich kalten Deutschland ins schon angehm temperierte Südfrankreich zu kommen. Und außerdem fehlen - wenn nicht gerade die Osterferien sind - noch die großen Touristenmassen. Selbst an der Fontaine de Vaucluse, die später im Jahr wegen der Touristen unerträglich ist, habe ich im Frühjahr schon sehr schöne Momente erlebt.

Mir fallen zwei Städte ein, die allerdings beide nicht direkt am Mittelmeer liegen. Zum einen Aix-en-Provence, das kulturell etwas zu bieten hat (Kathedrale mit Kreuzgang, Vasarely-Museum, Cours Mirabeau zum Bummeln), aber als Unistadt natürlich auch eine reiche Kneipenszene. Beides trifft auch auf Montpellier im Languedoc zu - Kultur mit Kathedrale, einigen weiteren Kirchen, Museen, Promenade du Peyrou zum Bummeln, aber auch Uni mit entsprechender Szene.

Neben Richerenches, das agnes 333 schon genannt hat, gibt es von November bis Ende Februar (also in der Trüffelzeit) auch in Carpentras einen großen Trüffelmarkt - dort behauptet man sogar, dass es der größte wäre.