Могу предложить Кирилловку на Азовском море (это Украина). Там куча недорогих баз отдыха, в середине мая вода уже ок. 20 градусов обычно. Сервис, прямо скажем, не ахти, но и денег за это много не берут. Пляжи песочные, море мелкое. В среднем, 2-х местный номер без питания с туалетом в номере стоит в это время гривен 150 (150*4=600 руб), с питанием немного дороже. Проезд на поезде 67, 97 или 207 Москва-Мелитополь, далее 80 км на такси (ещё гривен 100-200) или маршрутке (гривен 30, вроде, с человека). Собственно, Ваших 80 тыс Вам и на месяц в Кирилловке хватит на всю семью У меня недалеко от Кирилловки свой дом на Молочном лимане (село Шелюги, если что  ), поэтому те места мне хорошо знакомы