I think you are overstating both the "fear" and the "better than any other countries" aspect. The reality might be a bit more subtle.
Except in the first and the last year of Nazi rule, Nazi Germany was not particularly terroristic towards the majority of the population (those that were not Jews and were not active opponents of the regime). Stalin's post-1937 terror was seen as an exception afterwards. Post-WWII Eastern Europe was not a particularly scary place to live.
I am more familiar with 1980s Eastern Europe, so I will ignore the other examples.
I believe that these regimes fit the description as "totalitarian" reasonably well. However, there are some special circumstances that do not really apply to other totalitarian regimes, i.e. Soviet military hegemony. So these regimes are a bit of a special case.
How did they communicate that they are the best governments?
First off, you do not need to be the best government in every aspect. Being better in some crucial areas while not being abysmal in other crucial ones is OK.
And you can to a certain degree warp your people's perception of the severity of problems in other countries via media. That even works in a free press environment: you can have Americans convinced that Sweden is a total hellhole and Swedish people convinced about similar things re. America.
Eastern Europe had a high level of social security (no unemployment, no homelessness, no drugs) and low prices for basic commodities such as food and rent. Consequently, reporting about Western Europe constantly emphasized social problems. Eastern Europe had a constant lack of consumer goods and you had to. wait years to own a car or a telephone connection at home. Eastern Europeans could not travel the world. But are that not mere inconveniences compared to the danger of losing your home due to unemployment, or your children due to drugs?
Secondly, even if other countries are demonstrably better-off, it may still be possible to find reasons that any other government could not have done better in your own country.
E.g. after WWII, Western Germany got economic aid from the US, while the East got Soviet work crews that would move anything of value to the Soviet Union. Up to the railway tracks that were dug up and moved away. The first point (U.S. economic aid) was often played up in the media. The second one not so much for obvious reasons, but it was part of living memory.
Thirdly, people tend to be complacent and get used to a lot of things. The opposition was not able to organize, did not get access to the media and there were no opinion polls.
An individual may know that it is discontent with the state of affairs. But most people also know that there are always people who are content and people who are discontent. How does the individual know whether it is part of a vocal minority (in which case it would be dangerous, pointless and maybe unethical to openly show her/ his opinion) or part of a large majority?
This "silent majority" argument is still quite often used today, e.g. in Russia or until recently in Hong Kong. Though in the case of Eastern Europe in the 1980s, it was quite obvious that serious discontent was widespread among the population.
What about the "fear" aspect?
Of course the population was also controlled via fear. Just that this fear did not come in the form of prison or death, but in the form of educational or professional opportunities being denied for people who did not pay sufficient lip-service to the regime. I.e. such people would be denied the opportunity to attend university, which would only make them eligible for low-level jobs. Or if people who already had started their career were becoming rebellious, they would lose their jobs and be relegated to very low-level positions. E.g. engineers to the production line or to a janitor position.
And above this there was the clear message and experience that large-scale revolutionary or even evolutionary political change would not be tolerated by the Soviet Union, as demonstrated in East Germany in 1953, Hungary in 1956, and Czechoslovakia in 1968.
Finally, since this also seems to be a thread about book recommendations, I would recommend Milan Kundera's The Unbearable Lightness of Being, which describes all of this much better than I could.