I think the word that's more thrown around with late Russian Empire is more "absolutist", rather than "autocratic". While it's hard to understand today, in many ways the big debate in the 19th century wasn't "democracy" vs. "dictatorship", but rather "constitution" vs. "absolutism". The Russian Empire was—to my knowledge—the last major power in Europe to lack any sort of institutional check or similar limitation on the sovereign's will. Even the Ottomans and Qajar Persians got constitutions before the Russians did.

I am not an expert on Austria-Hungary or Russia, and so someone will chime in with more specific questions, but I have encountered the constitutional vs. absolutism question in studying the late Ottoman Empire. It's fascinating because it's one of those interesting areas where we encounter a familiar issue—how much participation should the people have in governing—but the terms of the debate are just completely different from our own.

In the Ottoman and Iranian contexts, the constitutional push built throughout the 19th century. I know the Ottoman context better. Here we get a series of moves that deeply reform the Empire (ending the Janissaries in 1822, the Gulhane Edict in 1839, Tanzimat reform period which kicked off with Gulhane) that didn't devolve power from the Sultan. In fact, most of these reforms increased the Sultan's direct power at the expense of the nobles and local notables—getting rid of tax farming, getting rid of the Janissaries as an independent power base, centralizing and rationalizing law, diminishing the power of guilds. I don't know about Austria specifically, but in the 19th century Russia had similar centralizing-modernizing reforms which tended to put more, rather than less, power directly in the Emperor's hands.

The Constitutional Movement in the Ottoman Empire first achieved success in 1876, though the First Constitutional Period only lasted until 1878, when the Empire returned to absolutism. How the Ottomans first got their constitution is complex, though it was largely Abdulaziz's failures and clear signs that the Empire's influence in Europe was declining, after the losses of Herzegovinia and Bulgaria. It was something of a palace coup and, as these things tend to be, it was a little bit easy-come, easy-go—once the next competent Sultan (there was briefly one who had a nervous breakdown) Abdülhamid II abrogated the constitution once he had consolidated power. But that's the general format of these constitutions: they are forced on absolutist ruler against their will and they have no choice but to accept these limitations on their power because of some acute crisis, frequently either a foreign military defeat or nationalist rebellions on the periphery or a financial crisis (or a combination of all three).

Constitutionalism in the Middle East got a surprising kick in the butt in the early 20th century. Nader Sohrabi (convincingly) argues that the Russo-Japanese War (1904-1905) gave a huge boost to constitutionalist movements around the world. Here, for maybe the first time, we see a modern, non-European state decisively defeat a modern, European state. (The Japanese got a constitution with the Meiji Reformation—they were still far from a democracy.) Political liberals around the global pointed out that Japan had a constitution and the modern system worked well, and Russia had no constitution and was incredibly backwards. This helped lead, Sohrabi argues, to a "wave" of constitutionalism.

Two of the most important parts of this wave were in the Ottoman Empire and the Qajar (Iranian) Empire. In 1905, protests broke out in Iran that eventually worked up into the Iranian Constitutional movement. The 1906 Iran Constitution, I believe, held until the end of the Qajar Empire in 1925 (when Reza Shah took over in a British-assisted coup). Similarly, the Young Turk movement ended Ottoman absolutism. Almost immediately after coming to power, they restored the 1876 constitution and ushered in the Second Constitutional Period which similarly lasted until the end of their Empire.

What I know from the Holy Roman-cum-Austrian-cum-Austro-Hungarian Empire is that after a crisis during the "Spring Time of Nations" in 1848 and then another one in 1867, the Emperor of the Austrian Empire was forced to agree to the Austro-Hungarian Compromise of 1867, transforming it into the famous dual monarchy Austro-Hungarian Empire. Exactly what counts as a constitution is complex so, for example, my understanding is that many historians consider there to be only 18 years of absolutist rule from when the uncodified traditions of Hungary were suspended in 1848 after the rebellion and the "re"instating of the constitution in the Hungarian half of the Empire, this time in formal, codified manner. Unwritten constitutions are not without precedent—to this day, the UK doesn't have single constitution but rather has a series of agreements and traditions from the Magna Carta to the Fixed-term Parliaments Act of 2011. And it's not just like that in some old nations—Israel, for instance, has a series of "Basic Laws" passed over the years. There's a really interesting book comparing this sort of gradual accretionary process in Israel, Ireland, and India called Making Constitutions in Deeply Divided Societies. But, however much the Austro-Hungarian Emperor was conservative, however much he hated reform and democracy, there were formal limits to his power and formal avenues for Austro-Hungarians have a voice in government.

This is where Russia was different. Despite repeated crises, the Russia czars managed to gradually reform—very slowly—throughout the 19th century without ever ceding any formal control to the nobility, the bourgeois, or the people more broadly. By around 1906, Russia was unique among the major power of Europe—and rare among the major powers of Asia—in lacking a constitution at all, lacking any formal limitation on the sovereign's power.

Eventually, the crisis foreign military, nationalistic, and financial crises caught up with Russia. They did get a constitution in 1906, as a last ditch effort to stave off the effects of the Revolution of 1905. However, as constitutions go it was incredibly weak—the Czar maintained the ability to veto any legislation for any reason. He quickly dismissed the first two dumas (parliaments) as “unsatisfactory” and then altered the electoral laws. Though after 1906 in a technical sense the Russian Empire was no longer absolutist, in the eyes of most, the Constitution—though it remained in effect—did little to curb the emperor’s power.

That "absolutism"—absolute power for the czar—is what set Russia apart even from other illiberal and autocratic 19th century regimes.

Edit: someone whose comment isn’t showing up reminded me that in the Russian context, “autocracy” is a term that the 19th century czars themselves embraced. I should have remembered this because I’m listening to Mike Duncan’s Revolutions podcast of the Russian revolution(s) and the amount of times he’s repeated the motto of “Orthodoxy, Nationality, and Autocracy”, you’d think it would have made more of an impression on me. That slogan dates from 1832 and technically belongs to the era of Nicholas I, but you see the deep influence of this pithy ideology on many of the subsequent czars as well, including and perhaps especially the ill-fated last czar, Nicholas II. While I might call the Austro-Hungarian Emperor “autocratic”, the Russian Czar carried among his titles “the Emperor and Autocrat of All the Russias.” When I talk about the debate about absolutism above, I am talking in terms of historical social science.

Because the political concept "autocracy" was introduced as a back-translation by European foreigners in the 19th century to specifically describe the Russian monarch's sovereignty. Starting with Ivan III, Muscovite princes referred to themselves as "autocrats" in the tradition of the Byzantine emperor. The Greek title "autokrator", meaning "self-ruler", was adopted by Byzantine rulers in the formula "basileús [kai] autokrátōr", meaning "emperor and autocrat", to designate the most senior of several co-emperors. Several Slavic rulers, such as Bulgarian emperors and Serbian kings adopted the literal Slavic translation of this titular formula "Царь и Самодержец" ("tsar' i samoderzhets") to lay claim to the imperial Byzantine title. In the mid-15th century the Moscow Orthodox Church pushed for the Muscovite grand princes to adopt the Byzantine title in order to give the Rus' monarchy ideological legitimacy and dissasociate itself from Mongol legacy and administrative practices. When Ivan III started to use the titles of "tsar'" and "samoderzhets" in international relations it symbolised his sovereignty as an independent monarch in the tradition of the Byzantine Empire as well as his realm's independence from Tartar overlordship. The adoption of the title "samoderzhets" therefore symbolised the elevation from principality to empire and has formed an important part of the Russian imperial founding myth ever since. The Russian Emperors kept this title until the very end of the monarchy in 1917.

At the end of the 18th and beginning of the 19th century the word "autocracy" increasingly appeared in European dictionaries, as foreigners tried to back-translate "samoderzhets" and resorted to the Greek term. But at this point "autocracy" was simply a synonym for sovereignty. Isabel de Madariaga traced the conceptual history of "autocrat" as a back-translation of the word "samoderzhets" in a very detailed article and asked the same question as you: "How and when did the word 'autocrat' come to be so systematically and uniquely associated with the Russian form of government?". She suggests that the answer consists of three reasons:

"First, the word samoderzhets forms part of the official titulature of the ruler of Russia, while its equivalent, "sovereign," is not added to the titulature of other European rulers, who may not have felt so strongly at any stage in their historical evolution the need to emphasize the moment when external sovereignty was achieved. Second, greater familiarity with the Russian language in the nineteenth century led to a renewed realization of the Greek origin of the word, and to an assumption by Western historians that "autocrat" represented a more faithful and accurate translation of the Russian samoderzhets, while leaving the actual content of the word "autocrat" rather vague. It was also a way of suggesting that Russia was different. Third, since "autocrat" became the usual appellation of the ruler of Russia at a time in the second quarter of the nineteenth century when the rigidly absolutist nature of the regime stood out in particularly glaring contrast with the increasing number of European constitutional monarchies, so the previously vague concept of autocracy acquired particularly authoritarian, even arbitrary overtones, and came to be associated almost entirely with Russia. Within Russia, too, samoderzhavie came to be regarded as a peculiarly Russian phenomenon, and the word was used increasingly in ordinary speech and writing to refer to "the government." This usage has been translated into e.g., English, where phrases such as "the policies of the autocracy" are frequently found. Little by little the concept lost all remaining vestiges of connection with the original idea of independence from a suzerain. As a result a new word had to be coined in Russian to express the concept of sovereignty in relations with other states. It was, as so frequently happened, borrowed from German: suveren and suverenitet. These foreign loan words are used to express "sovereignty" to this day. Is it too late now for us to shake off the habit of referring to the Russian tsarist regime as "the autocracy?""

Sources:

https://en.wikipedia.org/wiki/Tsarist_autocracy

https://en.wikipedia.org/wiki/Autokrator

Donald Ostrowski, Muscovy and the Mongols: Cross-Cultural Influences on the Steppe Frontier, 1304-1589 (Cambridge University Press: 2002).

Nina Kršljanin, "The Title of Samoderzhets (Autokrator) in Serbia and Russia: Two Ways of Byzantine Heritage Development", https://doaj.org/article/1680178e102d4e3490f43be2d19db355

Isabel de Madariaga, "Autocracy and Sovereignty", http://doi.org/10.1163/221023982x00911.