Сложно сказать наверняка. За все время, что мы ездим в Грецию, я ни разу не припомню, чтобы на домах были таблички или какие-то другие указания, что сдаются комнаты (по сравнению, например, с Хорватией, где такие таблички были). Возможно, надо было просто спросить.
Я бы, наверное, ориентировалась на маленькие управляемые семьями отели, которые присутствуют там почти везде и вряд ли бывают полностью заполнены в сентябре. Теоретически списки подобных мест проживания могут быть в местных туристических бюро, но, во-первых, не в каждом населенном пункте это бюро будет, а, во-вторых, оно легко может оказаться неработающим, это ж греки)))
В связи с вышесказанным я бы как минимум запаслась контактами такого жилья по маршруту, чтобы знать, куда бежать, если расспросы в тавернах/на рынках не увенчаются успехом. Или все-таки бронировала бы следующее место по маршруту, если это укладывается в вашу идею спонтанности ;-)
В любом случае, удачи. Прогулка по Кикладским островам - это должно быть что-то действительно чудесное.

С паромом получается странно. На некоторых сайтах-агрегаторах (например, www.ok-ferry.com/) можно прям сейчас купить билет на октябрь (правда, пишут, что паром не возит машины). При этом на сайте перевозчика, действительно, расписание заканчивается в сентябре, а в октябре стоят одни прочерки. Самолет тоже неплохой вариант, доберетесь вы точно быстрее, хотя, если исходить из того, что в аэропорт заранее, там ждать и прочее - мне кажется, выйдет так на так.
Про машину. Во-первых, на Мальте правостороннее движение, думайте сами, стоит ли оно того. Кроме того, там хороший общественный транспорт, нам его хватало. С другой стороны, скутер, наверное, было бы неплохо взять, чтобы не быть привязанным к расписанию автобусов.

Нет, Сардиния не только про пляжи, хотя пляжи там очень хорошие и море удивительно красивого цвета. Кроме пляжей и моря там есть всякие живописные городки и какое-то забавное непроходящее ощущение деревни в воздухе) Люди очень доброжелательные.
Праздники, к слову, там бывают не только весной/осенью. Мы, будучи в июне, попали в городе Порто-Торрес на Palio di Santu Bainzu, было очень красиво и интересно. В июле где-то там в другом месте ослы наперегонки скачут и, думаю, при желании можно еще каких-нибудь праздников найти. Сезон же, надо туристов развлекать)
В целом, у меня Сардиния не оставила после себя дикого желания вернуться, хотя там было очень хорошо. В любом случае, хотя бы раз на нее съездить интересно, от той же Сицилии она, на мой взгляд, все-таки сильно отличается.

На Эоловы острова.
Или на Мальту дня на три. Если туда не лететь, а паромом из Pozzallo, то в конце пути можно понаблюдать Гранд Харбор с воды ночью. Ну и гулять там много где приятно за счет компактности Мальты.
На Сардинию, на мой взгляд, ехать, имея неделю на Сицилии, - слегка странно. Если только галочку поставить, что на Сардинии были тоже.

"Отсутствие специальной подсветки у зданий" и "темно" - все-таки немного разные вещи. Фонари там вполне себе светят (или хотите сказать, что они все до одного выключаются часа в два-в три ночи?).
По поводу отсутствия красоты - видимо, она действительно в глазах смотрящего. Мы с семьей и друзьями несколько раз приезжали в Вену, гуляли по ней в разное время, в том числе и в темное время суток, в том числе и часов в 10-11-12 ночи. И мой опыт в отношении того, что никакой красоты в центральном районе ночью не увидишь, а также по поводу случайных приключений на свою задницу, с вашим не совпадает. На том, видимо, мы и остановимся.
*Не говоря уже о том, что мест, в которых с вами гарантированно не случится никаких неприятностей, в мире вообще исчезающе мало.

Мне сложно с вами спорить, разве что про Пратер, исходя из общих правил безопасного поведения, соглашусь. :) Ночной Хундертвассер на картинках выглядит, по-моему, как минимум забавным, но тут уж у каждого свой вкус и цвет, и вы в полном праве считать его выглядящим неважно.

А что не так с переулками внутри Ринга? Я там, помнится, ходила в одиночку достаточно поздно, правда, не в три ночи и эмм лет как бы не 15 назад :)

Если чувствуете себя в силах не спать всю ночь и готовы к тому, что придется тратить деньги, то, собственно, почему бы и нет.
И экскурсии, как нам говорит интернет, можно заказать, вот, например, ссылка из первой страницы гугла: www.maximatour.at/...96-2015-mar-14-11-08-10

И самостоятельно тоже вполне можно что-нибудь придумать.
Теоретически вы успеваете на последний САТ из аэропорта www.wien.info/...nter/city-airport-train (практически - можете и не успеть и должен быть запасной план).
САТ привезет вас на Wien-Mitte, откуда можно пойти пешком к Дому Хундертвассера, у которого, как я понимаю, никакой специальной подсветки нет, но даже в свете уличных фонарей будет видно, насколько он безумный)
Оттуда можно дойти до Пратера, вход туда свободный круглые сутки (по кр.мере на сайте они об этом пишут www.prater.at/...ralInformation.php?LI=1). Аттракционы вряд ли будут работать, но со стороны на то же колесо обозрения можно будет поглядеть.
Потом доехать на метро, если еще будет работать, до площади, где находится собор Св.Стефана, посмотреть на него, пройтись по Грабену, дойти до Ринга в районе Ратуши, посмотреть на Ратушу и пойти по Рингу, например, в сторону Оперы. Вполне себе получите впечатление от имперской Вены.
Общественный транспорт, если верить их сайту www.wienerlinien.at/...6533/channelId/-2000641, работает по очень гуманному расписанию: по выходным и праздникам метро доступно аж всю ночь, по будням - не всю ночь, но ходят какие-то ночные автобусы.
Короче говоря, если продумать пути перемещения/где поесть и если здоровья хватит ходить пол-ночи вместо того, чтоб в кровати спать, так можно неплохую прогулку сделать. Та же Ратуша с подсветкой ночью выглядит, по-моему, просто потрясающей, а днем впечатление от нее слабее.

Маршрут хороший, но, по-моему, может быть куда как лучше)

1. Ларнаку вообще оставляете в стороне? Там есть пара-тройка забавных достопримечательностей, которые, на мой взгляд, стоит иметь в виду. Если выбирать, то советую вам обратить внимания на церковь Св.Лазаря - если вы машину сдаете обратно в аэропорту, то имеет смысл заехать по дороге из Айя-Напы, посмотреть на нее и попить потом кофе на набережной. Кроме того на озере могут быть фламинго, а на дальнем его конце есть мечеть Хала Султан Текке, пятая святыня ислама. Внутри, честно говоря, ничего интересного, но вид на нее из-за озера хорош.

2. В Лимассоле что делать собираетесь? Немаленький город, да еще порт, море не очень. Ну, погулять можно съездить, конечно, в какой-нибудь Курион, но есть подозрение, что в августе долго гулять под солнцем не получится ;-)

3. Пафос
Многовато дней что-то на него) Про ущелье, честно говоря, ничего не знаю, из обязательных достопримечательностей - по-моему, археологический парк. Еще, говорят, очень красиво на полуострове Акамас, но тут надо читать, стоит ли туда ехать в августе и пройдет ли по тамошним дорогам ваша прокатная машина.

4. Троодос. На него я бы дней выделяла побольше. И, если нет необходимости упираться в Потамитиссу, возможно, смотрела в сторону Платреса или Пано Платреса, поближе к большинству пеших маршрутов. Смотрите, вот карта lovetroodos.com/...dos-walking-trails.html
Там есть очень забавные стильные отели типа New Helvetia, с камином (неактуален в августе, да) и с видами. Небюджетно местами, правда, и будут ли места на ваши даты - бог его знает.
Киккос у вас пропущен.

5. Про Никосию и север ничего сказать не могу, я бы, наверное, не стала их упихивать в одну поездку, т.к., по-моему, туда ехать долго, но, если хочется, чего б и нет.

6. И на Фамагусту стоит обратить внимание.

1. В Монтсеррат необязательно ехать автобусом.
Есть вариант электричка+канатка или электричка+горная электричка.
www.montserratvisita.com/...by-cremallera-and-train

2. Вот интересный список, что еще можно посмотреть в окрестностях Барселоны
lifeistravel.com.ua/...krestnostyakh-barselony
Выглядит симпатично, да и расстояния, прямо скажем, более разумные, нежели Ницца)

Езжайте в Грецию - там как раз будет и неплохой пляжный отдых и некоторое количество достопримечательностей поблизости. На Родос или Корфу или на Санторини (последний - не совсем про пляжный отдых, но ооочень красиво).

Италию не рассматриваете? В северной части Сардинии, например, тоже отлично можно совместить и пляж с водой красивого лазурного цвета и всякие познавательные прогулки по ближайшим городишкам.

Вообще, похоже, что вы и сами склоняетесь к Порту :-) Там романтичней, наверное, будет. Набережная, дома разноцветные, подвалы с марками портвейна на другом берегу, лодочки с бочками рекламные, трамвайчики старинные ходят. На каком-то до океана можно доехать, чтобы встретить закат.
Опять же, для одной ночевки, как раз нормально - самое красивое в городе вы как раз успеете увидеть)

В Луге не была, посмотрела, что, как пишут, там римские памятники, занесенные в список ЮНЕСКО. Они обычно очень впечатляют. И река, если верить картинкам, тоже есть.
Наверное, все-таки лучше в Порту. Хотя бы чтоб сравнить Испанию с Португалией, если вы в Португалии ни разу не были.