Слова "тем не менее" не используются как вводные.

ТЕМ НЕ МЕНЕЕ, частица и союз

1. Частица (часто в сочетании с противительными союзами «а», «но», а также в предложениях с союзами «хотя», «несмотря на то что», «пусть» и др.). Не требует постановки знаков препинания. 

Мюллер долго наблюдал за тем, как медленно, еле заметно, но тем не менее неуклонно лучи двигались по комнате. Ю. Семенов, Экспансия-I. Несмотря на то, что Ягозин был кровным детищем Петербурга… он весь тем не менее состоял из одной быстроты и юркости. Д. Григорович, Карьерист.

2. Союз (между частями сложносочиненного предложения). То же, что «но, однако». 

…Это были все-таки карты, несколько захватанные, затертые пальцами по краям, тем не менее невозможно было представить, что в них играли за столом... Ю. Бондарев, Горячий снег.

Большой толковый словарь

Выбор формы зависит от контекста. Ср., например: делать что-либо в обход начальника отделения (т. е. без согласования с ним).

Если имеется в виду, что сам начальник отделения совершал обход, то правила выбора между родительным и творительным падежом такие. К творительному падежу обычно прибегают, когда в случае употребления родительного падежа неясно, кто совершал действие. Например, в конструкции непонимание критика привело к скандалу смысл неясен: то ли сам критик кого-то не понял, то ли не поняли критика. Вот в этом случае и придет на помощь творительный падеж: чтобы подчеркнуть, что кого-то не понял сам критик, следует выбрать вариант непонимание критиком.

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

Марочные названия вин пишутся в кавычках с прописной буквы. Без кавычек и со строчной буквы пишутся названия сортов вин: шардоне, мерло, рислинг. Скорее всего, в ресторанном меню употребляются именно марочные названия, а следовательно, необходимы кавычки и прописная буква.

Что касается названий сыров, то они пишутся с прописной буквы при обозначении торговой марки и со строчной буквы в бытовом употреблении. Это так называемые интерпретационные орфографические варианты: пишущий волен сам выбрать тот или иной вариант написания, желая подчеркнуть, что речь идет именно о торговой марке продукта или, наоборот, о бытовом употреблении названия. На наш взгляд, в Вашем случае корректно написание со строчной буквы в кавычках (поскольку в качестве собственного именования выступает, в первую очередь, название блюда, а сыр указывается только в качестве ингредиента).

Аналогию между Госдумой и Российской Федерацией проводить не следует, поскольку написание названий государств и написание названий органов власти регулируются разными орфографическими правилами. В названиях государств с прописной буквы пишутся все слова (кроме служебных); в названиях организаций, учреждений, органов власти с прописной буквы пишется только первое слово и входящие в состав названия имена собственные, поэтому орфографически правильно было бы писать Федеральное собрание, Государственная дума (но Совет Федерации, здесь Федерация – имя собственное, т. к. выступает вместо сочетания Российская Федерация). Однако в официальных текстах (а на практике – в современной письменной речи вообще), вопреки орфографическим нормам, принято написание Государственная Дума и Федеральное Собрание.

Сокращения Госдума и Совфед могут быть использованы при неофициальном употреблении, например в прессе, в обиходной речи, но, разумеется, недопустимы в официальных текстах.

В приведенных примерах следует использовать существительные в форме множественного числа.

Имя существительное, которому предшествует два или несколько определений, указывающих на разновидности предметов, ставится в форме единственного числа:

1) если существительное не употребляется в форме множественного числа;

2) если существительное во множественном числе имеет иное значение, чем в единственном;

3) если между определениями стоят противительные, разделительные или сопоставительные союзы;

4) если перечисляемые разновидности предметов или явлений внутренне связаны, например, в сочетаниях терминологического характера;

5) часто, если определения выражены порядковыми числительными или местоименными прилагательными.

Имя существительное ставится в форме множественного числа:

1) если подчеркивается наличие нескольких предметов;

2) если имеется предшествующее определение в форме множественного числа;

3) если определяемое существительное стоит впереди определений.

Подробнее читайте в «Справочнике по правописанию и литературной правке» Д. Э. Розенталя.

Да, в подобных двухчастных заголовках ставится двоеточие. Оговоримся, что в справочнике по пунктуации Д. Э. Розенталя приводятся только примеры заголовков, состоящих из форм именительного падежа существительных, типа Многоэтажные улицы: спасение или бедствие? Между примерами из справочника и Вашим примером имеются и смысловые различия. В заголовках из справочника первая часть называет общую проблему, место действия, лицо, а вторая — содержит конкретизацию названного в первой части. В приведенном Вами случае в первой части заголовка приводятся чьи-то слова в форме прямой речи (хлесткая фраза, призванная привлечь внимание к новости), а во второй части поясняется, кто и при каких обстоятельствах сказал эти слова, и как раз это пояснение является новостью. Впрочем, полагаем, правило об оформлении двухчастных заголовков вполне можно распространить и на примеры вроде приведенного Вами. 

В этом примере наблюдается противоречие между смыслом и формой (структурой). Поскольку пословица не говорит в прямом смысле слова, здесь действительно можно усмотреть «характеристику прямой речи», то есть случай из примечания 1 к параграфу 48 справочника по пунктуации Д. Э. Розенталя. Однако на характеристику прямой речи указывают слова типа так или это, сравним: «Не давши слова — крепись, а давши — держись» — так говорит русская пословица. Наличие упомянутых слов позволяет поставить точку после цитаты, что существенно отличает такие конструкции от конструкций с прямой речью: «Не давши слова — крепись, а давши — держись». Так говорит русская пословица. В исходном примере такое сделать невозможно, так что по структуре перед нами конструкция с прямой речью, которую нужно оформить соответствующим образом.

В подобных случаях название города обычно играет роль подлежащего, а сочетание, указывающее на статус города, является приложением. По умолчанию между ними не требуется знак препинания: Столица России Москва вошла в пятёрку самых дорогих городов мира по цене элитного жилья. Если автор полагает, что адресату неизвестен статус Москвы, то приложение столица России приобретает поясняющий оттенок, и тогда нужно руководствоваться пунктом 3 примечания к параграфу 19.10 справочника по пунктуации Д. Э. Розенталя и поставить одиночное тире: Столица России — Москва вошла в пятёрку самых дорогих городов мира по цене элитного жилья. Если же условия контекста таковы, что статус города важнее, чем его название, то это название является поясняющим приложением: Столица России, Москва, вошла в пятёрку самых дорогих городов мира по цене элитного жилья.

Словарные рекомендации противоречат друг другу.

В «Справочнике по русскому языку: правописание, произношение, литературное редактирование» Д. Э. Розенталя, Е. В. Джанджаковой, Н. П. Кабановой (М., 2010) указано, что официальные названия республик обычно согласуются со словом республика (т. е. склоняются), если оканчиваются на -ия, -ея (в Республике Болгарии, с Республикой Индией), и не согласуются, если оканчиваются на -а или имеют форму мужского рода (в Республике Куба, из Республики Панама, в Республике Вьетнам).

В то же время в «Словаре географических названий» А. В. Суперанской говорится, что в сочетании со словом республика названия республик женского рода обычно склоняются (независимо от окончания): в Республике Колумбии, из Республики Кубы. А вот названия республик мужского рода несклоняемы в функции приложения (здесь противоречия между справочниками нет): из Республики Нигер.

Впрочем, в официальных документах все названия республик, выступающие в роли приложения, часто остаются несклоняемыми.