Из четырех пятизвездных отелей где я был - в трех стояло 2-3 компа с разшаренным модемом (или ИСДН). Скорость - сам понимаешь... С нормальными выделенками на побережье - туго. Есть ЖПРС, если купишь местную препейд-симку - будет стоить где-то 1.3$ за мегабайт. Работает практически без проблем.
Кроме того в поселке Текирова есть парочку интернет-кафе со всем офисным оборудованием (я там кроме всего прочего с флешки на ЦД фотки сливал - взяли 5$ (в 2002г.)). Цены на сам интернет у них уже не помню, но точно было явно дешевле чем в отеле...