They either refered to themselves as Rhomaioi (Ρωμιός) meaning Romans or Graikoi (Γραικοί) meaning Greeks. Initially the Graikoi were a subset of Rhomaioi, as a Copt in Egypt or a Bulgar could also be Rhomaios. As the empire contracted back into its core Greek lands, the two more or less became synonymous.

It's really only in the 19th century and onwards that the modern Greeks stopped calling themselves Romans and have readopted the ancient name of Hellenes (Έλληνες). During the Byzantine period and later that was reserved for the pagan Greeks of antiquity. But it has been adopted by the residents of the modern Greek state.

Even today you'll still occasionally hear someone use Rhomaioi or Graikoi. But it tends to be a poetic use, much like someone calling Great Britain Albion or Portugal Lusitania.