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

Названия улиц женского рода в сочетании с родовым наименованием улица обычно склоняются: на улице Кубанской Набережной, на улице Большой Покровской. Ср.: на улице Зацепский Вал (название мужского рода в сочетании со словом улица не склоняется).

Верно: на набережной реки Мойки.

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

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

Если требуется именно такое название улицы, то верный вариант улица Набережная Москвы-реки.

Слово река можно опустить, если не требуется официальное наименование набережной.