Boas...
Isso de fazer praia é muito relativo... já estive na Nazaré em Fevereiro e apanhei um grande dia de praia... tal como já estive no Algarve em Agosto e mal podia sair do apartamento...
A 1ª vez que fui a Palma foi em Abril e deu para fazer praia a semana toda... agora, pode ter sido "sorte", pois isto da metrologia, nunca se sabe, nem existem garantias de nada.
Agora, voltando à 1ª questão:
Nenhum dos destinos possui "praia" garantida em Maio, pois pode apanhar bom tempo, como pode apanhar chuva os dias todos e isso pode ocorrer nas Baleares ou nas Canárias... é uma época entre-estações e como tal ninguém pode dar garantias de nada, como tal, penso que deverá optar por um destino que lhe dei-a outras soluções.
Ibiza: tem animação, tem paisagens e tem praia se estiver bom tempo... com mau tempo, pouco mais há para fazer além de ir ver as paisagens, nem animação existe já que a maioria são bares/discos/festas ao ar livre.
Palma: tem animação (em Maio não tem de ter medo de ficar em magaluffe, pois ainda não possui qualquer confusão, quando fui em Abril fui visitar uma cidade no norte e posso dizer que era "assustador" pois eram milhares de edificios e não via vivalma... ou seja, existem zonas que só "acordam" mesmo em Junho/Julho para voltarem a adormecer em Setembro). Além da animação, tem paisagens (nesse aspecto é o melhor destino), visitas culturais e boas praias caso esteja bom tempo. Com mau tempo só tem cultura, paisagens e animação.
Canárias: em termos de praia não é nada de especial e nessa época começa a deslocar-se a corrente fria da antárctica em direcção ao norte (que provoca a deslocação para a nossa costa da "bela da sardinha") pelo que à água pode estar mais fria, mesmo com bom tempo. Pessoalmente não gostei de Tenerife, mas pode ter sido "mania" minha, sendo que não conheço Palma... Nas Canárias a minha recomendação vai sempre para Lanzarote. Em qualquer ilha possui animação (menos que nas baleares), cultura e paisagens... a recomendação de Lanzarote é só porque a ilha é muito diferente... é inexplicável... não parece nada de especial, mas a maioria das pessoas que conheço, depois de lá ir ficou "apaixonada" sem saber bem o motivo... Com bom tempo, pode dar um salto a fuertventura e apreciar uma das melhores praias da Europa.
Pelo que percebi o orçamento vai ter grande peso. Já ponderaram ir antes a uma cidade da Europa (tipo, em Itália)... pois optar por um destino tipicamente de praia em época "incerta" pode originar "amargos de boca" a menos que já sigam com a ideia de que será difícil fazer praia.