Что мы имеем из Новосибирска (цитирую себя же, так как поправок так никто и не внес):
Насколько я знаю, из Новосибирска есть прямые рейсы в:
- Европу: Болгарию, Германию, Испанию, Италию, Хорватию, Чехию;
- Азию или Северную Африку: Вьетнам, Египет, Китай, Турцию, Тунис, ОАЭ, Оман.

Отметаем:
- Не сильно жарко: Азию или Северную Африку. Можно оставить Эгейское побережье Турции, там не сильно жарко.
- хочется к морю: Германию и Чехию

Остается: Болгария, Испания, Италия, Хорватия, Турция. Некоторые фирмы пишут, что будет прямые рейсы на Мальту.
Из этих курортов и выбирайте, исходя из предложений, вписывающихся в Ваш бюджет.
$3000 - это 2200?, если я ничего не путаю. в Испанию, Италию и Хорватию на эту сумму не разбежишься. То есть "пролезете", но по притыку.