Da ich auch aus de Süden komme, würde ich natürlich auch Stuttgart empfehlen, ebenso Tübingen, da ist es auch wirklich schön! Außerdem eventuell noch das Ludwigsburger Schloß, das ist zwar auch nicht mittelalterlich, aber doch immerhin Barock (glaub ich zumindest

).
Heidelberg und München finde ich auch wunderschön... Ebenfalls empfehlen würde ich Würzburg!
Ansonsten fällt mir noch mein Heimatort Weil der Stadt ein - das kennt wahrscheinlich kein Mensch, aber wir haben dort sehr oft Touristen (Japaner, Amerikaner etc....). Weil der Stadt hat einen sehr schönen historischen Stadtkern um den Marktplatz herum, eine Gasse mit wunderschönen alten Fachwerkhäusern (das älteste ist von ca. 1490!)
Dazu kommt noch eine der größten erhaltenen Stadtmauer-Anlagen in der Umgegend. Auch zur Fasnet kommen immer mehr Touris, vor allem bei Amis kommt das wohl gut an! Natürlich ist es bei weitem nicht so gut erschlossen wie Heidelberg, Tübingen etc., eben einfach noch ursprünglicher!