Rhodes Old Town.
It's one of the few lived in Medieval towns, and is full to the rafters of history.
We stayed in a 4 star hotel called Mitsis Petit Palais (round the corner from the 5 star Mitsis Grand Hotel). We stayed about 2/3 years ago for a fortnight and didn't get bored of the AI food. The pool is small but it wasn't bad.
The best thing is that it's walking distance to the old town, and you can spend days wondering about the streets reading about the crusades etc.
It's walking distance to the beach, but it's not the best beach IIRC.