Если оставаться в рамках школьной грамматики — составное глагольное, которое отличается от стандартного составного глагольного тем, что модальное значение в нем выражено не глаголом, а словом категории состояния, из-за чего и появляется формальная связка.

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

Это предложение особого типа. Вот что говорится о нем в параграфе 78  полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина:

Конструкции с частицей не входят в восклицательные или вопросительно-восклицательные предложения, в которых часто присутствует частица только, напр.: Кто не знал этого человека! Что только не восхитило его на этой необычной выставке! Кому не известен этот дом? Чего в мой дремлющий то- гда не входит ум? Как не любить родной Москвы! Где только не приходилось ему бывать! Куда он только не обращался!

Такие предложения — по форме отрицательные — по содержанию всегда содержат утверждение. (Кто не знал этого человека! означает 'все знали этого человека'; Где только не приходилось ему бывать! означает 'ему всюду приходилось бывать').

Нормативными словарями современного русского языка такое прилагательное не зафиксировано. Однако в авторских текстах изредка встречаются прилагательные завтрачный (А что чем дальше, тем меньше становится человечков, с кем слово сказать, и только собирается в раковине завтрачная и обеденная посуда... [Анатолий Найман. Любовный интерес (1998-1999)]; Бассейн ― на минус первом. "Завтрачный" ресторан ― тоже. Это позволяет людям в плавках и бикини спускаться из своего номера на лифте сразу на минус первый и не шокировать голыми частями тела новых туристов (вдруг среди них старички со слабым сердцем или ещё какие скромняги) [Марина из Рязани. Марина из Рязани. Блогер города-полумиллионника (2015)]) и завтракательный (А завтракательные потребности где-нибудь удовлетворяются? — спросил я довольно ехидно [Владимир Войнович. Москва 2042 (1986)]; Принеси сюда мою волшебную завтракательную скатерть [Эдуард Успенский. Волшебник Бахрам (1973)]). 

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

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

Примеры употребления оборота: Но странно, эти самые первые, пришедшие ночью в Сталинград без оружия солдаты, отдавая хлеб защитникам города, обнимая и целуя их, словно были печальны, не веселились и не пели (В. Гроссман); Письмо было датировано самыми первыми годами нового века, и город, который стоял около даты, Ганка знал хорошо (Ю. Домбровский); В самых первых статьях о формализме «Правда» специально говорила о формалистских ошибках В. Мейерхольда, но он отнесся к этой критике, по обыкновению, несерьезно и безответственно (Ю. Анненков).

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

Вадим, склоняемость / несклоняемость не есть основной признак для классификации частей речи. Главный признак слов, объединяемых в одну часть речи, – наличие обобщенного значения, абстрагированного от лексических и морфологических значений всех слов данного класса. У имен прилагательных такое значение – выражение непроцессуального признака предмета: апельсины цвета (какого?) беж, юбка (какая?) мини и т. п.  Да, большинство прилагательных выражают это значение в словоизменительных морфологических категориях рода, числа и падежа – но далеко не все.

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

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

Внятная версия происхождения этого устойчивого выражения нам не встречалась. Однако в русском языке имеется изрядное число  разговорных фраз подобного типа, скрепленных внутренней рифмой: например, "откуда — от верблюда", "где — в Караганде", "муж объелся груш", "опять двадцать пять" и т. п. Можно, вероятно, назвать такие фразы образованными с помощью "фокус-покус приема". В словообразовании «фокус-покус прием» (другие названия — «прием рифмованного эха», «повтор-отзвучие», "эхо-конструкция", "эхо-редупликация") — это прием рифмовки созвучных слов, одно из которых является искаженным двойником другого. Наибольшее распространение этот прием получил в разговорной речи, например: штучки-дрючки, страсти- мордасти, гоголь-моголь, фигли-мигли и др. Причины того, почему в качестве отзвучия выбирается именно то, а не иное слово, крайне редко поддаются рациональному объяснению.

Варианты, о которых Вы пишете, — яркая черта старомосковского произношения. В речи коренной московской интеллигенции XIX — первой трети XX века согласный перед мягким согласным тоже был мягким. Наиболее последовательно это реализовывалось в сочетаниях зубных с мягкими зубными: [c']тена, [c']нег и т. д. В течение XX века это произношение постепенно уходило из живой речи, но сохранялось, например, в речи актеров, дикторов. Сейчас такие варианты в одних случаях уступили свои позиции новым нормам, но еще не ушли из языка совсем, они даются в словарях как допустимые, но устаревающие или устарелые: во[с]питатель u допуст. устарелое во[с’]питатель; [с]мех и допуст. устарелое [с’]мех. В других случаях они еще рекомендуются в качестве образцового литературного произношения: [с’]нег и допуст. младш. [c]нег.