Обычно в апреле уже хорошая купательная погода на Канарах, но с визой все-таки немного придется повозиться, хотя, если все документы предоставите, то не такая уж это морока
ЮВА (Малайзия, Филлипины, Индонезия) и некоторые страны Латинской Америки (Куба, Доминиканская республика, Ямайка) - теплые и безвизовые (правда, надо внимательно изучить, когда у них там сезон дождей наступает).