На конец июня, наверное, уже смело можно Майорку смотреть.
Обратите внимание на район Алькудии - там хорошие пляжи именно для маленьких. Основной минус такой дислокации - это относительно далеко от Пальмы и близлежащих курортов, где сосредоточены основные развлечения, и откуда удобно отправляться на экскурсии. Если жить в Алькудии и не брать машину, то организовывать экскурсионную программу будет неудобно. Вот хороший топик по Майорке:
http://forum.littleone.ru/showthread.php?t=4849651
На Кипре с середины и до конца июня, наверное, оптимальное соотношение температуры воды и воздуха. По Вашим критериям я бы посоветовала посмотреть отели в Ай-Напе Астериас и Dome (Dome Beach). Оба отеля на окраине (они соседние), на первой линии, у них хороший и не сильно многолюдный пляж. Доехать от отелей до центра Ай-Напы - не проблема, рядом автобусная остановка. Минус отелей может быть в их ценнике, который скорее всего не очень гуманный. По Астериасу несколько лет тому назад точно были отзывы на форуме (наверное, это уже в архиве).