Действительно, в начале 50-х годов государственный аппарат СССР начал перестраиваться. Выросла роль неформальных блоков, включая упомянутые «тройки» и «пятерки». Что касается упомянутых лиц, то и Маленков, и Булганин являлись достаточно грамотными и опытными государственными деятелями, не говоря уже о Берии. Увы, ни с кем из них Кузнецов так и не смог найти общий язык. Он предпочитал действовать по-прежнему лично через Сталина. Ему он докладывал оперативно-тактические задания на заложенные или закладывающиеся корабли. С одной стороны, Кузнецов, по его словам, «наблюдал доброжелательное отношение Сталина к флоту, с другой — видел его недостаточную компетентность в морских вопросах и нежелание прислушаться к морякам-специалистам». Так, Кузнецов настаивал на том, чтобы линкоры и крейсера имели сопоставимую дальность плавания, и на увеличении запаса хода эсминцев. Сталин отмахнулся, заявив, что «для пополнения кораблей всем необходимым будем иметь базы где нужно». Этими словами немедленно воспользовались судостроители.
К удивлению Кузнецова, взаимоотношения Министерства ВМФ с Военным министерством остались на том же уровне, что и в предвоенные годы. Главным виновником этой ситуации он считал своего старого недруга, заместителя председателя Совета Министров Булганина, курировавшего военные ведомства. Неприязнь он чувствовал и в личном общении, и при рассмотрении бумаг, которые Булганин возвращал с ничего не значащими, по мнению Кузнецова, бюрократическими резолюциями.
В начале 50-х постаревший Сталин уже не любил известий о каких-либо серьезных проблемах. Когда Кузнецов предупредил Маленкова, что готовит доклад о крупных недостатках в судостроении, тот посоветовал:
— Не следует беспокоить вождя!
Строптивый Кузнецов, разумеется, совету не внял. Ознакомившись с докладом, Сталин обратился ко всем присутствующим:
— Так ли это?
— Кузнецов сгущает краски! — бросил кто-то реплику.
— Ну, посмотрите! — Сталин и раздраженно бросил папку на середину стола.
После совещания Берия и Маленков попытались объяснить Кузнецову, что теперь вопросы следует решать по-другому, после чего отношения были окончательно испорчены. Булганин же, по словам Кузнецова, возненавидел его окончательно и передал эту ненависть Хрущеву, с которым состоял тогда в дружбе.
Увы, кратковременная опала не научила Кузнецова ни дипломатичности, ни умению системно решать вопросы в государственных инстанциях. Он по-прежнему предпочитал идти напролом, обращаясь непосредственно к Сталину, что прибавляло ему влиятельных врагов. И, по его собственному признанию, «потерпел фиаско. Не буду оспаривать это…».
Огромной проблемой для послевоенного ВМФ СССР, с которой сразу же столкнулся Кузнецов, став министром, была кадровая. Не хватало опытных командиров кораблей и соединений, квалифицированных руководителей для береговой инфраструктуры. Подавляющее число офицеров имели крайне низкую техническую подготовку. Кузнецову приходилось заполнять береговые инженерные должности выпускниками армейских училищ, выпрашивая их в соседнем министерстве.
Кузнецов предложил Сталину создать военно-морское училище самого высокого уровня — наподобие того, что существовало перед войной в Лиепае, куда набирали лучших выпускников политехнических институтов. Постановлением Совета Министров от 31 августа 1951 года в Ленинграде было образовано Высшее военно-морское училище инженеров оружия, имевшее реактивный, артиллерийский, минно-торпедный и химический факультеты. Начальником его был назначен опытнейший артиллерист контр-адмирал В. А. Егоров. Сталин приказал отдать под училище один из ленинградских дворцов, где прежде располагался Дом Советов. С особой тщательностью подошли к подбору профессорско-преподавательского состава, куда определили лучших из лучших. Забегая вперед, можно сказать, что эксперимент Кузнецова удался. Именно выпускники данного вуза впоследствии возглавили практически всю военно-морскую науку, а также стали основателями РВСН.
Вторым мощным центром подготовки научных кадров стало Высшее инженерно-техническое Краснознаменное училище ВМФ, где преподавали два академика, несколько членов-корреспондентов, два десятка профессоров и докторов наук.
Для береговой инфраструктуры Кузнецов добился создания строительного училища ВМС в Пушкине, специального военно-морского факультета Дальневосточного политехнического института во Владивостоке и специального военно-морского факультета Ленинградского инженерно-строительного института. Специализированные училища ВМФ открылись в Выборге, Риге, Ейске, Николаеве, Кронштадте и Ленинграде. Настоящей «вишенкой на торте» стал военно-морской факультет Ленинградской консерватории…
Таким образом, благодаря Кузнецову сформировалась система учебных заведений ВМФ, способная полностью удовлетворить потребности флота, в том числе на перспективу. А в перспективе было создание советского океанского ВМФ.