Мы ездили семьей (я, муж, ребенок 1.5 лет) в Грецию прошлой весной (с конца апреля по середину мая). Погода очень не устойчивая еще в это время, море только начинает прогреваться. Ближе к середине мая вода все еще была прохладная, но нам с мужем уже было комфортно плавать. А вот ребенок в воду заходить отказывался - ей было холодно.
Я сильно заморочилась поиском места с водой потеплее. Из ваших вариантов, как мне показалось, теплее всего вода на Родосе (+20...+22), на юго-восточном побережье. Примерно также, но все же чуть прохладнее, на Крите и юге Пелопоннеса. Вот
тут можно посмотреть прогноз температуры воды, очень наглядно
Мы выбрали в итоге южное побережье Пелопоннеса, там есть удивительные места и замечательные пляжи. Если заинтересуетесь Пелопоннесом - с радостью отвечу на вопросы.
Про достопримечательности - почитайте отчеты. Мне кажется, в любом уголке Греции можно найти много всего интересного.
Кстати, да. Чем восточнее - тем теплее море. Но я Кипр не рассматривала, потому что мы там уже были, да и по природным красотам, ИМХО, он сильно уступает материковой Греции.