Да, эти названия склоняются. Подробно см. в "Азбучных истинах".

Запятые не нужны. Слова по меньшей мере, как правило, не обособляются.

Правильно: Кот-д’Ивуар, Шарм-эш-Шейх.

Грамматическая норма: мы из одного района, из одного города.

Указанная запятая нужна.

Возможны варианты: в Кемерово и в Кемерове. Обратите внимание, что вводное слово правда обособляется с двух сторон запятыми, а однородные члены предложения, связанные союзом И, не нужно разделять запятой.

Если микрорайон назван в честь Кутузова, то верно: в Кутузово.

Слово гражданин многозначно. Основное его значение - 'лицо, принадлежащее к постоянному населению данного государства'. Также слово гражданин имеет значение 'житель города; горожанин', но оно является устаревшим. Поэтому в стилистически нейтральном контексте нужно писать жители.

Однако в особом стилистическом употреблении возможно и сочетание граждане Москвы, например: Но право голоса дано цензовым избирателям не для их личного использования, а для отражения в подаваемом голосе чувств и взглядов подавляющего большинства граждан Москвы (Из газ.). Также существует звание почетного гражданина Москвы.

Ни новосибирячка, ни новосибирчанка не являются нормативными вариантами. В образовании названий жителей участвуют суффиксы -як, -итянин, -ич, -ичанин, -чанин, -янин, -ец и др., при этом в каждом случае название индивидуально (зачастую обусловлено многолетней или даже многовековой традицией) и какие-либо аналогии (если сибиряк, сибирячка, то должно быть новосибиряк, новосибирячка) не проходят; критерий нормативности варианта – фиксация в нормативных словарях русского языка. В словаре И. Л. Городецкой, Е. А. Левашова «Русские названия жителей» (М., 2003) зафиксировано: новосибирцы, новосибирец, новосибирка.

Кажущаяся неблагозвучность названия объясняется некоторыми особенностями образования и функционирования слов – названий жителей. Парадоксом русского языка является малое количество названий женского рода, соотносимых с названиями на -ец (а именно этот суффикс является основным при образовании этнохоронимов, с его помощью образовано и новосибирец), при этом очень многие формы на -к(а) (в том числе новосибирка) вынуждены преодолевать некий барьер ненормативного восприятия.

В заключение отметим, что критерий «режет слух», «не звучит» и т. п. не может и не должен быть определяющим: все люди разные, и то, что «не звучит» для одного носителя языка, вполне «звучит» для другого – и наоборот. Именно поэтому существуют нормативные словари, задача которых – зафиксировать литературную норму и отделить правильные варианты от неправильных.