С прописной буквы пишется первое слово в официальном названии учреждения, организации и т. п. Правильно: Депертамент образования города Москвы. Но ср.: в примерах наподобие В департаменте образования обсуждали новую федеральную программу развития образования корректно написание со строчной буквы.

Правильно, конечно же, разуваться; глагол разобуваться (разбуваться) в состав современного русского литературного языка не входит. Трудно сказать, что это – то ли неосознанная речевая ошибка (т. е. носитель языка думает, что так правильно), то ли (что вероятнее) своего рода игра – нарочито неправильное, шутливо-просторечное произношение (наподобие «спинжака»).

Поскольку названия кораблей — условные наименования, наподобие названий литературных, музыкальных и т. д. произведений, в них  используются кавычки всегда, независимо от наличия или отсутствия родового слова: «Ниагара» и «Доблестный» отправились в путь (сравним: «Утро в сосновом лесу» было написано в 1889 году).