Екатерина Алексеевна, в отличие от многих начальственных дам, оставалась на своих высоких постах настоящей женщиной, не чуждой романтическим чувствам и увлечениям. У нее сложились дружеские отношения с некоторыми представителями творческой интеллигенции, включая Дейнеку. Его водитель Владимир Галайко даже называл ее лучшей подругой художника. По понятным причинам Владимир Алексеевич обращает внимание прежде всего на «автомобильную» составляющую отношений Дейнеки и Фурцевой: «Екатерина Алексеевна, она лучший человек у него была! Он часто встречался с ней. Она в машине с нами ездила, мы в Кремль ездили, и она ездила на „чайке“ вместе с ним. Я ехал следом. И она всё повторяла: „Саша, Сашка, Сашенька“. И он ей: „Катенька моя!“ Я ему говорю: „Чего вы так с ней, она же, это, с ней же и Хрущ дружит!“ А он говорит: „Да я, если надо, если захочу — завтра Хруща сниму!“».

«Да как вы снимете?!» — удивлялся водитель, никогда не скрывавший своей работы на КГБ. «Как? Создам мнение, и тут же его, это того!» — говорил Дейнека. Кстати, в конечном счете так и получилось. По воспоминаниям водителя, Фурцева часто бывала в мастерской у Александра Александровича на улице Горького. «Даже было так, что мы ехали вместе, а следом „чайка“ пустая ехала, а она ехала в нашей машине. Сказать, что они были в близких отношениях, я не скажу, потому что не то, что „не скажу“, а не знаю. Вот так», — признавался Галайко в интервью сотруднице Картинной галереи имени Дейнеки в Курске Марине Тарасовой. По всей видимости, Дейнеке удалось добиться симпатии власти на склоне жизни, став одним из фаворитов Екатерины Фурцевой. Мы никогда не узнаем, какими точно были у них отношения, но одно можно предположить с большой долей уверенности: и тот и другая были большими любителями заглянуть в рюмку. И это их, конечно, сближало.

По воспоминаниям водителя, Дейнека иногда разговаривал по телефону с Хрущевым: «Он не ему именно звонил, а позвонит секретарям, а потом его соединяли с Хрущевым», но о содержании бесед ему ничего известно не было. По всей вероятности, Дейнека обсуждал с Хрущевым оформление Кремлевского дворца съездов, где по эскизам мастера были созданы мозаичные гербы союзных республик СССР. Их можно увидеть и сегодня. Вот что писала об этой работе Екатерина Сергеевна Зернова: «Иные художники громоздили в эскизах многофигурные композиции, а он просто предложил гербы, соединив их развевающимися лентами, входившими в рисунок каждого герба. Получился непрерывный фриз и четкое членение. Очень красиво сочеталось розовое с золотом»[227].