When did the Romans finally acknowledge that they were living in an empire?

I would say it would have been with Domitian. Before him, the office of princeps was something that had been created by law. Sure, Augustus had been pulling the levers behind the scenes, but the authority he carried was justified through the Senate, so the appearance of the republic remained intact. His successors maintained this facade.

Domitian took many steps to minimize the Senate. He cared nothing for maintaining appearances regarding the republic, and was very vocal about being a monarch. He even went by the title of Dominus, which meant "Master" or "Lord." There was no hiding the fact that Domitian was a king.

I think this issue really is a historical linguistic problem here. The Latin term dictator is a nominalization of the verb dico, dicere. That is it would mean, literally, one who "dico"s, that is, one who speaks. Of course, this only provides the roots of the meaning, not the meaning it had acquired by the time under discussion, or even how it was used earlier. Assuming that a word's meaning is its literal meaning is an etymological fallacy.

It was in the reign of Caligula (37–41), the successor to Tiberius.

Whereas previous emperors had been honored as gods after they died, Caligula insisted everyone worship him as a living god. Other emperors were not as nuts as Caligula, but it definitely set the tone that the Caesar was the emperor. For example, Nero's coinage showing him wearing the radiant crown of a god:

Some emperors were philosophical about it. For example, Vespasian, who was actually a pretty cool guy, when he was near death joked, "I think I am becoming a god."

The term "emperor" comes from the Latin Imperator, which means sole commander or dictator. A dictator is someone who can make law with his voice. All of the Roman princeps since Caesar were considered imperators.

The first emperor to take the monarchical title was Heraclius.

After defeating the Persian Empire in 627 he took the title "King of Kings" which prevuously belonged to Persian king Khosrau II.

As such, starting from 629 he ordered to style him Basileos Basileion "King of kings" or simply "Basileos" "king". This continued with all consecutive emperors.

Besides taking the royal title he also changed the state language to Greek from Latin. Note that in Latin documents the title was borrowed from Greek rather than translated as "rex".

Emperor certainly was not monarch before Heraclius, in modern terms it was "dictatorship". Also note that the predecessor of Heraclius, Phocas was desposed by the senate, which indicates that at least senators did not consider the state to be monarchy.

Romans called their state "republic" even at the time of the Roman rexes. And the term "republica orbis" continued to be used for the whole Christian world in the Middle Ages.

The shift was indeed gradual and it was in the interests of the regime, when it was still taking root, to dissimulate that the Republic was intact and the emperor was just the first among equals. Augustus was a past master at this sort of game; Tiberius tried to play it too but with ill results. Later emperors felt less need to do so.

In fact, I am in favour of an early dating, i.e. I think that the Romans have wisened up to the change in the rules of the game quite early, by Nero's succession the very latest. Probably, already by Gaius's succession, as @TylerDurden has argued.

In any case, we have a very safe terminus ante quem in the form of Pliny's Panegirycus and his letters. Here is his first letter to Trajan:

The pious affection you bore, most sacred Emperor, to your august father induced you to wish it might be late ere you succeeded him. But the immortal gods thought proper to hasten the advancement of those virtues to the helm of the commonwealth which had already shared in the steerage. May you then, and the world through your means, enjoy every prosperity worthy of your reign: to which let me add my wishes, most excellent Emperor, upon a private as well as public account, that your health and spirits may be preserved firm and unbroken. source

This is not a noble writing to the first among his equals. This is a noble writing to his royal master. And what is crucial - Pliny does not feel any awkwardness over the fact. He is writing with the easy grace of a born courtier, and so we must conclude that the final acquiescence to monarchy must have occured at least a generation before Pliny himself.

While we do not have such candid and clear evidence for earlier reigns (perhaps then the veil of republican or quasi-republican fiction has not yet worn so thin), there are other bits of circumstantial evidence that can be adduced. For example, Svetonius tells us that Augustus took pains to maintain a fiction of elections for various magistracies:

Whenever he took part in the election of magistrates, he went the round of the tribes with his candidates and appealed for them in the traditional manner. He also cast his own vote in his tribe, as one of the people. (56.1)

As far as I know, later emperors are not known to have engaged in any such activity.

But Svetonius' next sentence is even more striking:

When he gave testimony in court, he was most patient in submitting to questions and even to contradiction. (56.1).

So Augustus actually appeared in court if summoned! For later emperors, this would have been unthinkable. (However, there were rare cases of the Senate trying the emperor's friends in a way that was rather discomfitting to the monarch, under Tiberius and even under Domitian, of all people!).

To sum up, I think that the shift to monarchy was actually likely to have taken place already in the reign of Tiberius (who actually stamped out the very last vestiges of Republican opposition).

There is one more point to bring up: what we are discussing here is the attitude of the elite. The common people were probably not very much concerned with constitutional niceties anyway. In fact, the ever-helpful Svetonius tells us that the common folk were not averse to the idea of a king already in Caesar's time:

But from that time on he could not rid himself of the odium of having aspired to the title of monarch, although he replied to the commons, when they hailed him as king, "I am Caesar and no king," (79.2).

Disclaimer: As has been repeatedly pointed out, this is a gradual shift that cannot really be pinpointed. Moreover, in my opinion, it hugely depends on how one interpret any of the several parts in this question.

Duringthe Principate period (27 B.C. – A.D. 284), emperors carefully maintained the façades of Republican government.

The senate continued its legislative, religious, diplomatic and judicial functions in the Principate ... The senate had a role in the legitimization of the emperor; both Trajan and Hadrian wrote to ask the senate to ratify their position. Galba also refused Imperial titles until conferred by an embassy from the senate. This is the paradox; the princeps held supreme power, yet some still insisted on acting as if the senate was of legal importance.

_{- Wilkinson, Sam. Republicanism during the early Roman Empire. Bloomsbury Publishing, 2012.}

Of course, it is obvious to us now that the republic had fallen and a monarchy had taken its place. Yet we should not project modern perspectives onto the ancient Romans.

To be sure, the State was organized under a principate - no dictatroship or monarchy. Names did not matter much ... The Roman, with his native theory of unrestricted imperium, was familiar with the notion of absolute power. The Principate, though absolute, was not arbitrary. It derived from consent and delegation; it was founded upon the laws. This was something different from the monarchies of the East. The Romans had not sunk as low as that. Complete freedom might be unworkable, but complete enslavement was intolerable.

_{- Syme, Ronald. The Roman Revolution. Oxford University Press, 1963.}

Part of the fiction of republicanism was the theoretical authority of the senate to elect emperors. Again, we recognise this to be rubberstamping a late emperor's choices and/or the army's decision. However, again, appearances were nonetheless kept up.

Originally the Emperor was elected either by the Senate or by the people, i.e. the army. Later this practice was modified, but not discernibly changed. In the early period, in the event of election by the army, the Senate at least recognized the army's choice. Under Gaius the day on which he had been proclaimed Emperor by the Senate was celebrated, and even Vespasian was recognized by the Senate ... by the third century, however, we observe recognition by the Senate being dispensed with.

_{- Mommsen, Theodor. "A History of Rome under the Emperors, ed. Thomas Wiedemann, trans. Clare Krojzl." (1996).}

Although the Empire had superseded the Republic, the state continued to maintain an illusion of constitutional continuity. It maintained republican daily activities and its rulers (for the most part) avoided monarchical pretences. That the republic had became a monarchy did not mean the Romans were obliged to realised what had happened to their ancient freedoms. While we know it had essentially became a monarchy, I would argue that the situation was familiar enough for a contemporary Roman to hold onto the fiction of a republic.

Nonetheless, realistically, public perceptions must have begun waking up to reality. This certainly happened by the time of the transition into Dominate, from the Crisis of the Third Century onwards. Unlike the previous era, Emperors abandoned the pretensions of republicanism. Diocletian's formal adoption of monarchical styles definitely could not have gone unnoticed.

Another point: I would argue there was a certain degree of doublethink going on during the late empire. Even while acknowledging the monarch and empire, Romans continued cling to the fantasy of a republic. When the Western Roman Empire finally fell in 476 A.D., the Senate sent the imperial regalia to Constantinople along with a delegation. The deputies carried with them an "unanimous" message addressed to the Eastern Emperor Zeno, in which the Senate:

[S]olemnly "disclaim the necessity, or even the wish, of continuing any longer the imperial succession in Italy; since, in their opinion, the majesty of a sole monarch is sufficient to pervade and to protect, at the same time, both the East and the West. In their own name, and in the name of the people, they consent that the seat of the universal empire shall be transferred from Rome to Constantinople; and they basely renounce the right of choosing their master, the only vestige that yet remained of the authority which had given laws to the world. The republic (they repeat that name without a blush) might safely confide in the civil and military virtues of Odoacer; and they humbly request, that the emperor would invest him with the title of patrician, and the administration of the diocese of Italy."

_{- Gibbon, Edward. The history of the decline and fall of the Roman Empire. Vol. 6. J. & J. Harper, 1829.}