Название склоняется и при наличии родового слова город (г.): в г. Владивостоке.
Что касается необходимости родового слова: А. Э. Мильчин и Л. К. Чельцова в «Справочнике издателя и автора» отмечают, что «сокращение г. (город), как и полное слово, рекомендуется употреблять ограниченно, главным образом перед названиями городов, образованными от фамилий (г. Киров)».
Таким образом, правильно и общеупотребительно: во Владивостоке. А варианты в г. Владивостоке, в городе Владивостоке следует характеризовать как специфически канцелярские (т. е. употребительные преимущественно в официально-деловой речи).
Запятая ставится.
Эти фамилии склоняются (как мужские, так и женские).
Кавычки не нужны; между названиями городов ставится тире с пробелами: Москва –Владивосток, Красноярск – Новосибирск – Томск.
О склонении географических названий см. в «Письмовнике».
Томск: томичи – томич – томичка; томичане – томичанин – томичанка; томчане – томчанин – томчанка. Владивосток: владивостокцы – владивостокец.
Тихоокеанский флот - Владивосток;
Черноморский флот - Севастополь;
Балтийский флот - Балтийск (Калининградская область) и Кронштадт (Ленинградская область).
Кроме того, в состав ВМФ России входит Каспийская флотилия, главная база - г. Астрахань.