В прошлом году мы с женой снимали за 15 гривен с носа (170р в день получается) на Меньшикова, было клево - большая комната в которой днем прохладно, 10 минут пешком до песчанной бухты и Херсонеса.
Думаю цены должны быть в этих пределах (хотя в сентябре наверное дешевле). Район вокзала не советую - там как-то хреновато. Лучше тут или левее:
http://www.wikimapia.org/#lat=44.596763&lon=33.488903&z=15&l=1&m=a&v=2
(Меньшикова или "Летчики")
Выходите на площадь перед вокзалом, и на вас кидаются толпа старушек(они обычно тусуются под/на пешеходном мостике через пути). Главное - правильно выбрать. Основной критерий - горячая вода и расстояние до моря. Только на 1-2 дня обычно неохотно сдают.
Где в районе Севастополя можно с палатками стоять я без понятия. Имхо всякие вояки и лесники будут докапываться... Вернетесь - поделитесь опытом.
Катер до Инкермана ходит от Графской пристани и стоит 2 гривны.
А на северную сторону вообще 1 гривна, только в форты не пускают все равно
На автобусе можно легко добраться до пещерных городов (правда до Мангупа последние 5км пришлось на попутке).
Еще совершенно замечательно в Балаклаве. На базу подводных лодок правда только за деньги

Но там и без этого есть на что посмотреть. Добиралово: до пятого километра на троллейбусе, дальше 10 минут на маршрутке.
Вообще, Севастополь - город русской славы, там замечательно и народ золотой - рекомендую.