The evidence of how Roman subjects used to address Roman emperors comes from letters, either those that survive as literary texts - such as Pliny the Younger's letters to Trajan or M. Fronto's to various members of the imperial family - or then those that were inscribed on stone on public, such as petitions and letters by communities and individuals from various corners of the empire. Therefore, especially documents of the latter kind, might exhibit a degree of self-conscious, ostentatious formality and flattery that might not be used in oral exchanges, but probably any oral addresses would have followed more or less similar tracks.

There did not appear to be any one "correct" way to address the emperor, but many different respectful titles and admiring adjectives could be used. In the surviving documents, esp. at the start of a formal letter from someone who is not in frequent, personal correspondence with the emperor (esp. common in epigrachic, i.e. inscribed, texts) the full name of the emperor/emperors was used, e.g. "To emperor Caesar Marcus Antonius Gordianus Pius Felix Augustus." Then, when the emperor is personally addressed (or pleaded to) in the body of the text, we commonly find sugared superlatives like "most divine" or "most sacred emperor", where emperor could be imperator in Latin or basileus (also means "king") in Greek. We also find the emperor very commonly addressed simply as "Caesar", which was more or less just a different word for emperor, a honorific name that every emperor adopted. Also, "our lord" or "master" (dominus noster) was common, increasingly so towards the Late Antiquity, when epigraphic monuments to emperors start to omit the long litany of names and instead just address the emperor(s) as "our lord(s)".

One presumes that the further away in rank the speaker was from the emperor, more formality and more fancy titles was required. So, the surviving "private" letters from senatorial rank can be a bit more "familiar" than haughty stone monuments; Pliny the Younger titles his letters to Trajan simply as "to emperor (imperator) Trajan" rather than using his full name. When he addresses Trajan in the letters, he often calls him "master" (domine) or "the most excellent emperor" (optime imperator). The letters of Fronto to Marcus Aurelius, Antonius Pius and Lucius Verus are also illuminating. Quite often he, like orators in some other texts, might just address a sitting emperor with a short version of their name, but usually including the "imperial" name Augustus that emperors adopt once they take the purple, e.g. "Antonius Pius Augustus". Marcus Aurelius and Fronto, who was his tutor, became very close and over the years the way he addresses Marcus in the letters changes a little bit. In the early letters, when Marcus was not yet an emperor, he calls him domine ("master" was not, of course, a title limited only to sitting emperors in Rome, but in use in various social contexts), and in the last years of Fronto's life he addresses Marcus with different titles which are a mixture of affectionate warmth and reverence to the sitting emperor; "Caesar", "my own Caesar", "my master Marcus Caesar" etc. etc. So, their close friendship did not make much of a difference in the ways of address; then again, the emperor was formally thought to be a "friend" of every senator and very affectionate vocabulary could be thrown around by both parties even with senators who were not personally close to the emperor, so the way Fronto speaks to Marcus Aurelius might just as well be how any upper class Roman spoke to him without any etiquette breach.

I have written a longer response about body language and greeting Roman emperors previously: TL;DR is that Republican and High Imperial Romans considered grovelling before a monarch a despicable and humiliating Eastern custom, and Roman citizens (at least) did not practice it habitually. As far as we know, there was no specific gesture that was required when meeting the emperor, though respectful demeanour and recognition of his authority by, for example, not sitting in the presence of the emperor etc. was required. There is some evidence that bowing and "groveling" started to be practiced in imperial courts during Late Antiquity and in the Byzantine Empire, though.

There is one source that I managed to find and I am sure that other people will find more. Greek is my native language and it is also the language in which the excerpt is written so I'll do my best to translate it. "Liutprand enters Constantinopole for the 2nd time: In the 4th of June we reached Constantinople and we were opposite the golden gate waiting on horseback until 11 ó clock while Nikeforos was confirming our ambassadorial status and he judged us to be not deserving of entering the city on horseback. He commanded the guards to escort us on foot to the open marble mansion that I mentioned earlier. In the 7th of June I was led to the kouropalates and logothetetes Leon (the brother of Nikeforos ) and then proceeded to sparr about your Imperial Title(referring to the holy roman emperor). For he didn't call you emperor but a Rex that comes from regem. However when I made the remark that the meaning is the same but the word is just different he answered saying that I didn't come here for peace but for sparring. Source : S.Karageorgios The Holy roman Empire tome A pages 499-501." The Important thing is that a high ranking official of the eastern roman empire wouldn't recognise the title of emperor for the ruler of the Holy roman empire. That is because he recognised as roman emperor the one in Constantinople therefore he would refer to the eastern roman empero as well...Emperor however there are sources that refer to the eastern roman emperor as Caesar how ever not Augustus because the title of Augustus was slowly being abandoned during the late seventh and early eighth century AD and being replaced with Βασιλεὺς πιστώς έν Χριστό (basileus faithful to jesus) so one would call the byzantine emperor as either just Emperor or Basileus or Caesar.

As to whether they would grovel or bow well there is one source from Liutprand himself about that and it goes like this "Infront of the imperial throne stood a bronze tree coated with gold where chirping of various birds could be heard. The throne of the Emperor was so neatly constructed that from where I stood seemed as if it were low on the ground how ever later as I got closer it got higher. Huge lions from wood or metal coated with gold stood guarding the throne and looked as if they were roaring with an open mouth. In this room I was led in front of the emperor who was being carried by two eunuchs . When I entered the lions were roaring and the birds were chirping. Later after I bowed three times in front of the emperor I lifted my head up and saw him sitting on a giant throne that almost touched the ceiling of the room and he was dressed differently from before. Liutprand antapodosis Book 4 chapter 5" So there you have it During an audience with the emperor a person had to go up to him (seeing the grandeur of the throne room) and bow three times before they could even look at him. I hope I answered your questions as vest as I could

Edit: logothetetes (Λογοθέτης του δρόμου ή του γενικού ) was one of the highest ranks one could achieve in the eastern roman empire this applies to the kouropalates ( κουροπαλάτης) as well

Edit 2 : it is important to note that in Greek emperor translates to Αυτοκράτωρ (Autocrat) which translates to the one who has power.