First of all, I can't speak on the case of Roman or (later) Byzantine rulers. I'll limit my response to later medieval Latin Europe (circa 800-1500). Power in medieval (western) Europe was much more decentralized than anything imaginable to us. With no internet, telephone or even regular mail service, medieval monarchs had to delegate their God ordained authority to their vassal noblemen underlings, in exchange for military service when called upon. Especially since the time of Charlemagne's coronation by the papacy (800), medieval European rulers were believed to not only have a kind of a divine approval to rule, but were viewed as semi-divine themselves. For example, the king's touch was believed to cure certain diseases, most notably scrofula. Likewise, the coronation ritual was performed by a high church official (thus demonstrating a divine imprimatur), and involved a royal anointing ceremony, echoing that of King David in the Old Testament. By our modern standard of state power & authority, such "power" was mere window dressing. A medieval king could not efficiently extract resources from his subjects, first of all, due to the insufficient monetization of the economy (most of the wealth pre 1500 was locked up in land), paltry record keeping, lack of bureaucracy and poor infrastructure. Fundraising, especially in times of crisis, was limited to irregular collection of tribute, taxing of trade in the few urban centers, or outright extortion from the few places that held concentrated wealth (precious metals) like churches or monasteries.
A 21st century notion of "free speech" simply did not exist prior to the advent of wide literacy, print, and the development of a modern civil society. Based on the records we have, for the vast majority of medieval Europeans (ie, illiterate peasants), social criticism was most likely limited to immediate loci of authority: the nobility on whose manor they toiled or the local parish priest to whom they paid the yearly tithe.

TL;DR. What you're asking is a very, very broad question that requires a prior explanation of the functioning of medieval society before it can be in any way addressed in any significant detail. A western, liberal, 21st century definition of "freedom of speech" was simply not part of the discourse in medieval Europe.

Some very basic literature on medieval rulers and medieval society just off the top of my head: Marc Bloch, Feudal Society (2 vol) (Chicago: University of Chicago Press, 1964); Ernst H. Kantorowicz, The King's Two Bodies: A Study in Mediaeval Political Theology, (Princeton NJ: Princeton University Press, 1957).

So, I can't comment on much of your question at all, although /u/DieMensch-Maschine (whose name fucking rocks by the way) appears to have gotten some of it covered. But I can give some of it a shot I suppose

To start with, I'd like to challenge the assertion that you're making in the first place. Who exactly claims that ancient states were some sort of totalitarian Stalinist regimes? The idea is extremely anachronistic and in no way accurate. True, Suetonius likes to gossip about all the people someone like Caligula put to death, and Tacitus goes on at some length about what a tyrant Domitian was, but there's quite a bit about both accounts that we can take exception to. For one thing, both writers (and Tacitus in particular) have very open political agenda, which doesn't necessarily make their testimony suspect (as many people uneducated in classical historiography should probably learn before they dismiss all ancient sources as "inaccurate"), but it does mean that they're spinning things and omitting. In particular the testimony that certain emperors were tyrannical in Suetonius and Tacitus almost always focuses on a very small segment of society, mostly the (dying) aristocracy. Suetonius mentions that several "tyrannical" emperors were quite beloved by the vast majority of the population, and looking back on their legislation and so forth there appears to have been a great deal of benefit and attention directed at the lots of ordinary citizens with a lot of these emperors. Secondly, Tacitus in particular likes to cherry-pick. Tacitus' testimony about Domitian is very suspect, because he really has an ax to grind. Clearly Domitian was not a nice guy and he was obviously a tyrant, but Tacitus, since both he and his relatives had been attacked by Domitian, really likes to make him the devil incarnate.

So, anyway, moving on. I really have difficulty finding any real evidence for much of the premise of the question, including the idea that "non-democratic governments" are free of this behavior. What of Athens towards the end of the Peloponnesian War, when oligarchic supporters were hunted down and violently attacked for simply holding views opposed to the current regime? And where do we draw the line between what is democratic and what isn't? Would the brief oligarchic rule in Athens during the war count as a democracy of sorts? It was rather a lot more inclusive than many forms of oligarchy attested elsewhere. Does what little we know about the Carthaginian constitution make them somewhat democratic? Aristotle seems to be inclined to consider them partially democratic, but even the Roman state in the 1st Century, B.C. is decidedly more democratic than that. And speaking of the 1st Century Romans, what of them? Many people who don't really know what they're talking about claim that the Romans were not a democracy, but the presence and rights of the comitia show this to be quite false--the comitia, and not the aristocracy, were the only ones who could pass laws and that acted as law courts.

Let's move on again though. Let's limit this to regimes that are quite clearly autocratic, or at least monarchies. I'd argue that there are very few of these past the Bronze Age--the Principate, the Achaemenids, and many Hellenistic states are the only ones I can think of. Even then the satraps held an enormous amount of power and freedom in the Achaemenid state and the pretense of Republicanism in the Principate does not mean that the senate and comitia were completely for show, they held some administrative and minor legal importance, and the emperor generally only personally stepped in if he absolutely had to. Still, we have problems here.

The big problem is that you simply can't have a Stalinist regime before the modern period. When people do not have instantaneous communication, when transportation by rail, car, or plane is unavailable, when and when a significant portion of the population lives far from the center of authority (in rural areas or cities other than Rome or what-have-you) and maybe even local centers of authority it's simply not possible to impose such a regime. You can police the aristocracy, sure, and you can focus on particular groups of dissidents or troublemakers, but imposing restrictions on freedom of speech, on expression, on political opinions? Absurd. Some farmer out in a senatorial province is perfectly capable of insulting the emperor, and even people in Rome can (and did) insult the regime frequently. Even in a state like the Achaemenid state, where we have the presence of the "King's Eyes" this kind of thing is impossible--the Great King's spies can't be everywhere at once, they can't be policing the farmers out in the fields and all the urban poor. Those spies are there to watch people of political importance--satraps, local aristocrats, members of court.

In addition, this sort of totalitarianism is simply not borne out in the textual record. True, Syme rather convincingly wrote of the Principate as resembling a totalitarian regime, particularly compared to the late Republic, a period of unprecedented political freedom, but he quite correctly never goes so far as to say it is totalitarian or that it really parallels such governments in any meaningful way. The presence of the witty and subtle attacks on Augustus in Virgil, Horace, and other contemporaries, and the not-so-subtle attacks (most lost) in Pollio or Livy show perfectly well that freedom of speech was quite alive, as was criticism of the regime. And I do not buy the rather weak (and generally not accepted argument) that Augustus and his fellow emperors were too damn stupid to notice--Augustus was no fool, and even if he was Maecenas knew perfectly well what Virgil and Horace were trying to say, and allowed it (even encouraged it, despite being a die-hard Augustan!) anyway. Lucan went from being Nero's yes-man to one of his most ardent detractors. Lucan's fate is of considerable interest to us in this question, I think, so I'll address it. After Lucan turned against Nero, writing poems attacking his policies and insulting him personally, Suetonius reports that Nero was perfectly satisfied with simply ignoring Lucan and at worst trying to convince people not to read him. It wasn't until Lucan really went nuts and began publishing very political works that Nero began to really have to turn his attention against him--Vacca refers to some incredibly provocative (even by Roman standards) jabs against Nero (although it's contested whether these are supposed to be actual references to Lucan's verse, or whether Vacca is quoting someone else), and we know that Lucan wrote an ode to Nero's alleged burning of the city. Even then, Nero was satisfied with a ban against the publication and reading (which means public reading--Roman writers generally had their works read publicly before an audience, often to promote their works) of Lucan's work, a ban which was not particularly well-enforced, since Lucan continued to publish long after its enactment (one expects it was rather half-hearted). Lucan was not ordered to commit suicide until he entered into open political revolt, joining Piso's failed conspiracy against Nero (who I'm sure jumped for joy at the chance to legitimately remove him). That Nero put up with Lucan for so long, a man who is possibly the most open political dissenter in Latin poetry, speaks a great deal towards the idea of free speech in the Principate. And while we have the occasional nutjob like Caligula, whose murders were more or less indiscriminate and not politically-motivated, it's incredibly rare to see someone executed under the Principate for simply expressing a contrary opinion. Executions and exiles of important political figures took place upon the uncovering of plots, and many of these plots were able to be organized rather openly because of the ability of people to speak and congregate freely. And though we find punishments for people who disagreed with the emperor or (more usually) openly flouted his will, these punishments are almost always minor unless it's plotting--relief of office for Agricola, or for the numerous magistrates who tried to go against Augustus' quite strict laws regarding magisterial powers. Plus there's the fact that so many plots succeeded, or got very far in their planning. A real Stalinist regime doesn't have things like that getting very far, because it's simply impossible for plotters to congregate in anything resembling a public environment and private conspiracies will be penetrated by spies. This very fact, combined with the countless voices of dissent we have preserved in literature (many, if not most of them, quite high profile) speaks a great deal towards the reality of autocratic, totalitarian regimes in Rome.

True, the emperor had an enormous amount of power. He could, and if necessary did, enact capital punishment on people. He could, and often did, punish people for dissenting opinions. But not in a Stalinist way, and certainly not in a way that could realistically brand him as a "horrible dictatorship." That we have so many texts in dissent, and that political opposition and debate are attested as continuing all throughout the Principate in a ferocity unimaginable in Stalinist Russia shows quite clearly that it is simply not the case that this was the kind of world that we're looking at