Byzantine is a neologism entirely, they did indeed consider themselves exclusively to be Roman, and not only in a limited fashion or as a successor state, but as a direct continuation of a state that had merely lost part of it's former territory.

There was little need for reconciliation, as Christiany had taken root far before the fall of the western empire. Though that new faith definitely shook the Roman empire (and is considered one of many factors of it's fall, because it damaged the former belief in the divine nature of imperators), that crisis occurred well before the fall of the western empire. When Rome fell to the germanic 'barbarians', it was already a Christian city, practicing what we would see today as Orthodox Christianity (as it was pre-Schism).

Also, it's important to keep in mind that the notion of duality between Rome and Constantinople existed well before 476; the Greek half of the empire had long wholly embraced the empire and was in many ways dominant well before the fall of Rome. The eastern Rome considered itself the true seat of power even before the fall of the west. It's not surprising they clung to their identity afterwards, and if anything, our use of 'Byzantine' today has more to do with the politics in western Europe and specifically the Holy Roman Empire later on. In the west, there was an obvious desire post-schism to reduce the importance of the eastern claims in order to make the Holy Roman empire and the Papacy more legitimate. Terminology like 'the empire of the Greeks' was used in the west, but people living in Constantinople would have considered that offensive and belittling. The use of 'Byzantine' instead of 'Roman' would insult them still if any were still around to complain about it.

In short, while there was a real conflict between Roman pagan beliefs and Christianity, that conflict long predated 476, so it did not impact faith-wise what we see in modern terms as the successor state of the Roman empire. For a thousand years afterwards, it's mainly religious conflict (based largely on what could be seen as Papal overreach and forgeries) that eroded the view that Byzantium wasn't Rome anymore in the west; it never eroded that view in the east until the fall.

This is a fantastic question! I'm going to give you a couple of thoughts by pointing to several ways we can think about Byzantine Christian imagination and interaction with the pagan past. Note here now that it is very hard to generalise: fifth-century Byzantium was a very different place from its eight-century incarnation, and what an ordinary person might see and know about their world would likely differ from what a monk or an educated aristocrat might know. I'll try to draw attention to these nuances, but keep this in mind as you think about issues of identity.

One source we might use to think about identity and pagan/Christian mythology are chronicles - in particular, I'd like to talk about world chronicles. Built on the Eusebian model from the 4th c., these are extremely interesting accounts that usually start right with the Creation and go on to trace history to various points of time. Chronicles are in general extremely interesting and the way they are built and structured usually tells you a whole lot about how its author imagines the world: for instance, Eusebius writes the chronicle in four parallel columns, each of which records events in a different place at a parallel time. This is crucial, as he imagines in essence what is an interconnected world: even though events are happening in a different place, they are happening in the same framework, which is the divinely established Christian time. In this way, all is connected. Eusebius is perfectly fine setting the pagan past into this Christian framework: for instance, he holds that Moses was roughly contemporary with the mythical Argive king, Inachus, his son Phoroneus, and Ogyges. He notes down the capture of Troy and Aeneas (although he is tactfully silent about the whole Venus business). Whether pagan or Christian, for Eusebius all belong in one Christian timeline that starts with Creation and will end with the apocalypse.

Let's look at another world chronicle - but a much later one. George Synkellos wrote in the early 9th century, and was consciously reacting to previous chroniclers. He is in particularly concerned with two approaches: that of Julius Africanus, who refused to deal with non-Christian history altogether, and the Eusebian way, which tried to harmonise traditions in a way I described even while admitting at times difficulties with the biblical chronology. George, in his time, has not much patience for either: his chronicle consciously attempts to harmonize classical and non-Christian tradition in a way that proves the veracity of the biblical account. You still get Aeneas and Troy and Romulus: but George, while he recounts the tradition, also does a whole of rationalisation. For instance, with Romulus and Remus, he states that they were said to be sons of Mars: but then he gives you a whole lot of other possible parents for Romulus and Remus, from Aeneas himself to Odysseus and Circe, Latinus or Italus (drawing on a bunch of ancient writers, who notoriously could not agree on who really founded Rome) while also saying it was possible that Rome was not founded by Romulus at all, but by someone different altogether - some of the candidates are Remus or Aeneas. This captures two ideas: first, even the ancient Romans and Greeks weren't really sure who founded Rome, and second, George essentially seems to comprehend these as narratives that might not be true. When he says 'Latinus was said to be the son of Herakles', he is relaying information to the reader while signaling that while these people thought Herakles was a demigod, he of course was not. Chronicles used to be dismissed as historical sources: but all this tells you they were quite clever pieces of writing!

But what did you think about Aeneas et al if you were the average Constantinopolian, strolling around your city? Well, it's possible you had no idea who they were. Constantinople in particular was a place littered with ancient statues that Constantine brought over: you had, for instance, Mars and Venus (ancestors of Romulus and Aeneas) standing over the hippodrome. But by the eighth or ninth century, which is when the Parastaseis syntomoi chronikai was composed, people - even somehow educated ones - were perfectly fine with saying that they were in fact Adam and Eve. Some scholars would say that this was a conscious reinterpretation of these statues: I'd humbly suggest that its likely these people had no bloody clue that this was Venus. What they saw was a naked lady: the only naked lady in their mythology that was appropriate to be exhibited there was Eve. The Parastaseis syntomoi chronikai, which I referred to, appears to be a tourist guide that takes one around all of these statues and it's extremely interesting: you can learn, for instance, that some people thought the statues housed demons, since they were so big and - the art of building these monumental statues having been lost in the meanwhile, likely in the crisis of 7th and 8th c. - no one could imagine how they came to be. What then people appear to do with these statues is reinterpret them in an extremely interactive way: for instance, one statue was said to house a demon of fever, so if you'd caught it, you were advised to go and throw rocks at it. That's one way to solve the dilemma of your pagan past!

This is by no means an exhaustive answer: if you are interested in more, I'd suggest you go and read George or Eusebius to see what they are saying in particular about the stuff you are interested in. Maybe you'll come to different conclusions! For more background on Byzantine and Christian chronicles, see The Oxford History of Historical Writing Volume 2, edited by Sarah Foot and Chase Robinson, as an introduction.

For Byzantine ancient statues, a lot of work has been done on this: I remember liking Cyril Mango's Antique Statuary and the Byzantine Beholder and Liz James' "Pray Not to Fall into Temptation and Be on Your Guard": Pagan Statues in Christian Constantinople, but I'm sure you can google more stuff.