As Hildegard of Bingen, author and abbess, preached in Cologne around 1163:

[These people] will come with ashen faces, and, clothing themselves in sanctity, will ally with the great lords...They will walk about in black robes, with proper tonsure, and will appear to men as serene and peaceful in all their ways. Moreover, they do not love greed, and they do not have money.

[...] And in their secret selves, they hold abstinence as so great a virtue that they can scarcely be reproved...Thus they appear in public as if they were filled with sanctity, and say with mocking words: 'Before now, all other people who wanted to remain chaste burned themselves up like roast fish. But no pollution of the flesh or lust dares to touch us, because we are saintly and filled with the Holy Spirit.' (trans. Baird & Ehrman)

Hildegard wrote text after text extolling those primary Christian ascetic virtues: charity, poverty, chastity. She lived during a time when religious leaders getting the ear of secular princes was a really big deal. (Medieval German emperors had a habit of appointing their own popes if they didn't like the one in Rome.) When Hildegard says "proper tonsure," she means that this group of people conform in all ways to the appearance and values of Christian clergy. What she describes is...pretty much how she advises people to act.

...but...

But the devil is within these men, revealing himself to them in the obscuring lightning, just as he was at the beginning of the world before his fall. And he makes himself like the prophets.

...When the full gamut of this error has been run, these people will everywhere persecute and exile the teachers and the wise ones who remain true to the [Christian] faith.

Wake up!

Which is one very big and demonic asterisk.

Hildegard is acting here as apocalyptic prophet (how she was most famous in her own day), warning her audience to shape up or God would call down his wrath. This and some other medieval prophecies contain the most basic elements of dystopia and dystopian literature:

• a literary depiction of an ideal society realized but corrupted
• mixed with the notion of human improvement
• packaged as a warning to readers and listenerers

But if Hildegard's letter to the Cologne clergy seems kind of like an Epsilon Minus Semi-Dystopia, there's good reason. Our stereotypes of dystopia are linked to very modern developments: scientific engineering of human biology (eugenics, genetics, cybernetics) and societal engineering of human behavior (collectivism, behavior control). Some Cold War-era political philosophy even holds that dystopia is necessarily a police state: that the drive for societal and human perfection (utopia) will always end in mass, punishment-based control over behavior.

So I think of Hildegard's Cologne sermon and related medieval prophecies as the pre-history of dystopia, one defined above all by its religious nature, frustratingly insufficient worldbuilding, and message that ultimately, God is in control.

Thomas More usually gets credit for popularizing the genre of utopian literature in 1516, and 1600s England in particular produced a lot of literary utopias. But while plenty of these are written in a satirical vein, scholars trace the beginnings of the satire of utopia, as a concept, only to 1726 in Jonathan Swift's Gulliver's Travels. The key target here isn't politics so much as foolish human faith in science (a la the utopian writings of Francis Bacon):

The author permitted to see the grand academy of Lagado. The academy largely described. The arts wherein the professors employ themselves.

[The professor]'s employment, from his first coming into the academy, was an operation to reduce human excrement to its original food, by separating the several parts, removing the tincture which it receives from the gall, making the odour exhale, and scumming off the saliva.

Even with occasional bursts of satire in the realm of fiction plus some nonfictional treatises, people were still generally writing about idealized societies as the ideal through most of the 1700s and 1800s. But in the late 19th century, Gregory Claeys argues, two new hot-ticket strategies for achieving human perfection came to dominate literary portrayals of envisioned societies: eugenics and socialism. This could still be in an idealist mode, but often it was ambivalent: Ellis James Davis' Pyrna: A Commune, or, Under the Ice (1875), for example, presents a bubble society of perfect community, charity, and harmony that is achieved in part by euthanasia of unfit children. And sometimes it could be outright dystopian, as in the very subtly titled Red England: A Tale of the Socialist Horror, which combines fears of socialism with eugenics-related fears by stripping away citizens' control over their relationships and parenting

From the point of view of history of dystopian ideas, I think it's worth calling attention to the importance of child-raising and family issues in late 19th/early 20th century dystopian writing, which tends to play less of a role in the dystopian writing we read today (new or not). We see a little bit of this at the fringes of books like Brave New World (1932) with the Bokanovsky process and the scene with the Delta toddlers, but it's more of a peripheral horror-by-extrapolation. The world of a modern dystopian classic like The Giver (1993) is built on what looks like cozy, happily-chosen, functional families; in Hunger Games, family is what the state can't control.

So essentially, the length of the history of "dystopia" as an idea is as long as you want it to be--depending on how you define the word. Hildegard's sermons, the angelic pope prophecies, the prophecies of the last world emperor: later medieval Christianity envisioned more than its share of leaders who appeared virtuous but ended up as puppets through which Satan ruined the world. Or maybe the drive to perfect human existence through biology and behavior must always and only end in a surveillance and punishment-ruled totalitarian state. Whether or not we have always been at war with utopia is up to you to decide.

Hi! Very interesting and broad question.

I will answer from my area of expertise: medieval literature, and more specifically Scandinavian medieval literature. First, I must emphasis that no text from the medieval Scandinavian literature can be defined as a "dystopic" narrative. None of these texts is explicitly about describing the worst possible society, but some of the most important examples of medieval Scandinavian literature are explicitly concerned with politics and the role of the state. As such the authors described and contrasted good and bad examples of government. Your question is specifically about whether bad form of government was characterized as authoritarian. I must also specify that the examples of novel you provided are depiction of totalitarianism, which is not exclusive with authoritarianism but not equivalent either. I will solely speak of authoritarianism and not of totalitarianism.

So, is authoritarianism presented as a political evil? As often, it depends: one of the earliest examples of Medieval Scandinavian literature is the Gesta Danorum (the deeds of the Danes) by Saxo Grammaticus, which was written around 1210. The work is a very lengthy history of Denmark through its heroes and kings, the first half of the work is mainly legendary while the second dwells with more historical matter. In this text Saxo speaks a lot about the institution of monarchy. Most of the time his kings are portrayed in a rather negative ways, one of the negative traits of the bad rulers is tyranny. According to him, the king Harald bluetooth has enslaved people to haul a huge stone as a memorial to his deceased mother. This act of tyranny is presented as one of the major sources of his fall as well as an immoral example of government. It is however not only the authoritarian aspect of his action which is at stake, Harald is also criticized for neglect, prioritizing this non urgent task over his military duties. Excessive authoritarianism is only one of the flaws of bad government, and Saxo is primarily concerned with Christian morality and civil peace. Above all, the good king is the one who listen to the church (Saxo was himself working for Absalom, the archbishop of Lund) and one which preserve peace in his kingdom. One way to preserve peace in the kingdom may be to bring war outside of the kingdom. For instance, Saxo had nothing against authoritarianism used against the Baltic pagan people which often partook in pirate expeditions against Denmark. When describing the Danish expedition against those pagan Balts he portrayed with a lot of admiration how the Danish invaders destroyed the pagan sanctuaries and forced the Baltic people to practice Christianity. To him, authoritarianism is not an intrinsically bad thing, it can be used to attain good means, but it can certainly be abused if performed for self-interest. In that regards authoritarianism is not intrinsically bad if it serves the Church or is used to defend the country from civil war or foreign invaders. It can however be abused if performed for self-interest.

Another, more famous, example of medieval Scandinavian literature on political power is the Heimskringla (often called The History of the Kings of Norway in English) written by the Icelandic chieftain Snorri Sturluson around 1230. In this massive piece of literature Snorri often describes the struggles between local political rulers and the kings, which tried to establish their political rules all over Norway. It is not always easy to know what Snorri’s personal opinion on the matter is. The narrators of the Icelandic sagas are presented as a neutral point of view merely witnessing the events unfolding before his eyes. Of course, despite this seemingly neutral point of view the texts often convey political opinions. As Saxo Snorri is not against every form of authoritarianism, the first king of Norway, Harald Fair-Hair is a generally positive character, and his main achievement is submitting every Norwegian chieftain to his authority, often with violent means. The unification of Norway is presented as an honorable deed, but it must be noted that Snorri, as other Icelandic authors, present the colonization of Iceland as the result of Harald's harsh rules: wealthy farmers, were dissatisfied by their sudden, and mandatory submission to a king, and preferred to settle on a desert island rather than suffer his rule. (I must specify that historical and archeological data show that the tyranny of Harald is not the cause for the settlement of Iceland, but Icelandic authors certainly believed it was.) These Icelandic settlers are hardly portrayed as negative rebels, and Snorri empathizes with their desire for independence and self governance.

On the other hand, Snorri also depicted some of the most praised rulers of Norway as authoritarian kings. For instance, one of the first king to introduce Christianity to Norway, Olaf Tryggvason, would be a fanatical tyrant by our modern standards. Snorri describes him bullying and torturing chieftains unwilling to accept Christianity and his rule (submission to his rule being mostly equivalent to conversion to Christianity). Olaf is even portrayed as trespassing some of the most holy rules of the medieval Scandinavian society such as hospitality, as he used violence against his hosts. The same is for his successors, Saint Olaf, who achieved Norway's conversion and bullied the last rebel chieftains into submission. I would personally argue that according to Snorri, the two Olaf kings were not entirely positive and that some of their actions were meant to be perceived as excessive, but in anyway their reign must be seen as globally positive as they introduced Christianity in the kingdom. Once again, authoritarianism, even excessive, may be an acceptable mean to attain desirable goals.

Yet the authority of the king is not always presented in a positive light, and one of the most famous passage of the Heimskringla is a harsh criticism of the ambition of Norwegian kings to rule over Iceland:

‘The reason I have had little to say about this business is that no one has called upon me to speak about it. But if I am to give my opinion, then I think that the course for us dwellers in this land is not to submit here to the taxes paid to King Ólafur and all the burdens such as he has imposed on people in Norway. And we shall be causing this deprivation of freedom not only to ourselves, rather both to ourselves and our sons and all our families that inhabit this land, and this bondage will never go away or disappear from this land. So, though this king may be a good man, as I firmly trust that he is, yet it will happen from now on as it has before now, when there is a change of ruler, that they turn out differently, some well, some badly. But if the people of this country wish to keep their freedom, which they have had since this land was settled, then it will be best to grant the king no foothold on it, either in possession of land here or by payment from here of specific taxes which may be interpreted as acknowledgement of allegiance. But this I declare to be quite proper, that people should send the king friendly gifts, those who wish to, hawks or horses, hangings or sails or other such things that are suitable to send. It is making good use of these things, if they are rewarded by friendship. But as for Grímsey, there is this to say, if nothing is transported from there that can be used as food, then a host of men could be maintained there. And if a foreign army is there and they come from there with longships, then I think many a cottager would feel that oppression was at hand.’

Here quoted in the translation of Alison Finlay: Snorri Sturluson, Heimskringla II: Óláfr Haraldsson (The Saint), trans. Alison Finlay and Anthony Faulkes, vol. 2, 3 vols. (London: Viking society for northern research, 2014). pp. 143-144.

When the authority of the king threatens the interest of Iceland, or of the wealthy farmers, it is soon perceived as illegitimate or tyrannical.

This is only a superficial overview of the topic and much more could be said on that matter. To sum it up I could say that medieval Scandinavian authors were not aiming at describing dystopic societies. They however portrayed imperfect examples of rulership. One aspect of what made a ruler imperfect, or frankly bad, was a misuse, or abuse of his authority. The authority of the king was however perceived as a safeguard against political chaos and civil war. Unlike in modern novels, the most dreadful political danger was civil war and political chaos, not tyrannical governments. In that regards, strong kings have been seen a necessary inconvenience against the greater danger of generalized violence.

EDIT: lot of typos and grammar

I can help you with your corollary question from my own area of study, namely philosophy. An important source for the mid-20th century dystopian fiction, especially Orwellian fiction, is the 18th century concept of the panopticon, what you could call the birth of the concept of a surveillance society as we recognise it today. It was developed by the 18th and 19th century philosopher and social theorist Jeremy Bentham. Bentham is known as one of the first philosophers to fully develop an ethical theory of utilitarianism. Explained in short, classic utilitarianism states that the most ethical choices are those that create the most happiness for the most people.

Now, the idea of the panopticon is to design institutions like prisons (its most famous application, but also schools, hospitals, factories, etc) in such a way that a central point in the building can keep watch over everything that goes on in the place. In other words; Big Brother is watching you.

Often, when we look at a prison or other building designed according to panopticon principles we get a feeling of an oppressive, authoritarian, centralised control where privacy is nonexistant. But this wasn't how Bentham viewed it. According to Bentham, this way of building would be better for both the people being watched and the watcher. it would create more goodness for more people than the older methods of incarceration, healthcare and employment, as it would force the public to follow the rules without the guards having to resort to physical violence as was often the norm back then. He saw it as more humane in that regard, as compared to the more brutal approach from the aristocratic regimes at the time, and it fit his utilitarian views.

In the mid-19th century, prisons in the UK actually started being built with panopticon principles in mind, and it became more popular as time went on, and with it surveillance principles became wider known. Writers like George Orwell did not see Bentham's ideas in the same positive light. And that's of little surprise considering the level of surveillance and censorship he was put under by the British government due to his leftist politics. So he took those ideas of a surveillance society and set them in the negative light many people often refer to today.

So in short, the idea of the 'Thought Police' and Big Brother is definitely older than Orwell and his contemporaries. But back when it was first developed in a way that is recognizable to us it was seen as almost utopian. Orwell however, as someone who was intensely surveilled, thought different and gave us the dystopian interpretation of those principles that we usually use today.