In short, most Byzantines never actually thought that the republic died or that they were living under some sort of theocratic absolute monarchy. The reason why emperors around the rule of Aurelian adopted less republican titles was because of the cultural and political emphasis on the military that occurred because of the instability of the 3rd century. After that however, Byzantine political thought very much embraced the idea of the republic akin to the attitudes of the Principate. If you want a deeper dive into this, check out A. Kaldellis's The Byzantine Republic (having recently read it, I can recommend it and will pull from it for this post). And given that they were essentially the same state, the Byzantines used a lot of the older Roman imperial and republican titles, albeit in Greek forms. Here are some examples of titles not reserved for the emperor that remained in use (note that these offices often did not have the same functions as in the republic or the early empire):

Patrikios (πατρίκιος): Patrician

Magistros (μάγιστρος): Magister

Hypatos (ὕπατος): Consul

Anthypatos (ἀνθύπατος): Proconsul

Praitor (πραίτωρ): Praetor

Interestingly, there was an explosion of new and old (reconstituted) titles in the wake of Basil II's expansion of the empire in the 11th century, such that the number Byzantine court titles went from 11-21 in that century alone (Take a look at J. Shea's 1st chapter, "Byzantium at the turning point" in Politics and Government in Byzantium for an in-depth analysis through the lens of seals).

Additionally, some titles for the imperial family and the emperors are likewise derived from the republic and early empire:

Kaisar (Καῖσαρ): Caesar

Sebastos (σεβαστός): Literally, "one who is august", so "Augustus," another form, "Augoustos" (Αὔγουστος) was used during the tetrarchy, while sebastos was the Byzantine imperial court title after the 11th century

Autokrator (αὐτοκράτωρ): Equivalent to "imperator," reserved for the emperor

Of course, the primary imperial title was "Basileus" (βασιλεύς). The word is translated often either into the word "emperor," in the context of the Byzantines, and "king" usually for anyone else (This was the title of Alexander, the Hellenistic kings, and the modern Greek monarchs. However, in the Byzantine perspective, most people wouldn't have equated it to the modern word "emperor", which we usually think of as a centralized, authoritarian or absolute ruler sometimes with religious overtones of divine right akin to Louis XIV for example.

In fact, the Byzantines actually had a word, among others (tyrannos, τύραννος, for example), for this sort of despotic and tyrannical ruler, from the Latin word rex (for some reason I can't find anything that will tell me what exactly the Greek equivalent was). This word was a clear pejorative meant to evoke the bad, anti-republican, rule of the Roman kingdom. The term was also often used for western-European rulers to signify that they were lower in rank to the basileus.

A great example of this is in Liutprand of Cremona's account of his 2nd embassy to Constantinople in 968 CE. Liutprand was the Bishop of Cremona and was sent to the emperor Nikephoros II Phokas in Constantinople to negotiate a marriage between him and the eventual Holy Roman Emperor Otto II. Nikephoros II was supposedly a horrible diplomat, was intent on rejecting the proposal, and treated Liutprand horribly (according to Liutprand's very entertaining account). Liutprand describes how Nikephoros's brother referred to the reigning Holy Roman Emperor Otto I (Otto II's father):

I was led into the presence of his brother Leo, the marshal of the court, and chancellor; and there we wearied ourselves out in a great discussion concerning your imperial title. For he called you not emperor, which is Basileus in his tongue, but, to insult you, Rex, which is king in ours. And when I told him that the thing signified was the same although the terms used to signify it, were different, he said that I had come not to make peace but to excite discord;

Additionally, "Basileus," and the imperial office, had very few religious connotations. Many people think that the Byzantine emperor was believed to have been God's earthly representative, and thus connect it with the term "Basileus," but this is incorrect. To put it short, the idea of the emperor as God's chosen was only ever applied after the fact and only in certain situations. If an emperor ruled well, anyone could say God picked them, if they ruled terribly, then they were usually deposed without a second thought. No emperor could ever tell their subjects that they were empowered by God and expect everyone to unquestionably obey them. Moreover, these attitudes did not apply to the imperial office itself. To add a modern example, many Americans believe that Donald Trump was appointed by God to be president, and crazier people thought Barack Obama was the Antichrist, but does that mean the office of the American president is a religious one? No.

Consider this quote by 9th century patriarch Photios on the nature of politics and God's role in it (Letter 187 [Lines 186-193] found in The Byzantine Republic page 184):

our Savior and God had no intention to establish political regimes or any of their orders. For he knew, he knew well, that human beings would be able to provide these things for themselves from their own experience, that necessity would easily furnish them with instruction on a daily basis, and that the errors of those who came before would prevent future generations from making the same mistakes... The Savior's intention was only a concern for the salvation of souls.

There's much more to say on the topic but what I want to detail is that the imperial office, and the word Basileus cannot really be perfectly equated to our modern idea of an "emperor." This is the case with many non-Western European monarchs (another example is the Emperor of Japan or Tenno, 天皇). Moreover, the Byzantine Empire itself was not really an empire in the modern sense either. The emperor was not absolute or divine and could be deposed without any major moral or legal objections. Likewise, republicans ideals were very much present in the empire and the Byzantines still believed they lived in a res publica (or in Greek, politeia, πολιτεία).