This topic is very divisive and even now historians are still arguing about whether the fall of the Western Roman Empire was decisive or not. The main schools of thought can be divided between those who emphasise continuity and those who emphasise the empire's catastrophic collapse. I lean on the side of continuity, though I do agree that in material terms, there was a decline of living standards for the western Mediterranean, though it was a lot slower than what catastrophist historians such as Bryan Ward-Perkins suggested (I personally think that the big economic collapse was in the early seventh century in the East, and mid-sixth century in the West, due to the plague and Eastern Roman reconquest of the West).

The key thing here is to understand that the Eastern Roman Empire was still fundamentally Roman. They thought of themselves as Romans, their neighbours called them Romans and Latin was still the official language of state (it gradually shifted to Greek, reaching a critical point in the reign of Heraclius in the early seventh century). For them, in the immediate aftermath of Odoacer's victory, very little changed. He was already a Roman military leader, his army of German foederati were already in Italy and in Roman service, and even the last emperor in Italy, Romulus Augustulus was half-barbarian himself. Odoacer promptly sent the imperial regalia to Constantinople and only called himself king of Italy, which still makes sense within an imperial framework - there was no question of actually challenging the eastern emperor. Zeno probably wasn't even that shocked, since the Western Empire was going through emperors at a fairly rapid pace and he had other issues to worry about, such as usurpers and Christian schismatics - having Odoacer as a temporary ruler of Italy didn't actually change that much after all, the same had already happened to every other western province!

For decades "barbarian" leaders were seizing power everywhere in the West and all nominally acknowledge imperial jurisdiction. Gold coins were still minted with the image and name of the emperor and as mentioned here, Gregory of Tours talked about how Clovis was awarded the title of the consul and went around showing it off (not too surprising, as he basically inherited the title of master of soldiers in Belgica, he was a Roman official even though the empire had no actual power in Gaul!). Gregory is a bit late to talk about contemporary reactions to the Fall of Rome (he wrote in the late sixth century), but he arguably collected oral sources and we have more immediate sources, such as the letters of Sidonius Apollinaris and Avitus of Vienne, which all paid due reverence to the Eastern Roman Emperor and demonstrated the existence of highly active Gallo-Roman elite. In Spain, there were also two revolts seemingly by Roman pretenders backed by senators, whilst in Africa the Vandals quickly established friendly relations with the Constantinopolitan court. For ordinary people, we have little to no sources, but I think it's a good bet to extrapolate that they thought very little had changed. The same Germanic Arians ruled them as before, even as Roman institutions and Romanised elites (bishops and landowners) continued to thrive.

In fact the first source we have that even mentions the fall of the West as anything other than just a change of regime was in the Chronicle of Marcellinus Comes, which was written around 520 in Constantinople. Marcellinus basically said that 476 was the end of the Western Roman Empire, a shift from previous chroniclers, who only talked about a change of regime. This is perhaps important because by that stage the Ostrogoths had invaded Italy and overthrew Odoacer, on the orders/advice of the Eastern Empire. Theodoric of the Ostrogoths had then started to build a very real alternative to traditional Roman domination, building alliances with other western powers and very plausibly trying to cement his dynasty's control on the western Mediterranean outside of the imperial framework, perhaps explaining why Marcellinus suddenly wrote about 476 very differently, since from his perspective, Theodoric's regime was very different from that of the previous generation, which people would have thought very integrated into the Roman world.

As a final point, I'd also like to add that historians only really start to call the Byzantines the Byzantines after the Arab Conquests of the seventh century, as the loss of the majority of their empire basically forced significant changes upon them, such as the theme system to organise its military and a less estate-orientated economic system.

Hope this helped! Feel free to ask any questions :)

Complete tangent, but I'm interested on the basis of a recent question on war nomenclature- where are you from, and when did you first hear the term "American-Hispanic War"?

According to Gregory of Tours, everyone during this time still thought and acted as if it was still the Roman Empire, however, we know from texts like Gregory of tours History of the Franks life was changing as this new idea of Christendom began to form. In fact Notker the Stammerer was probably one of the first European Historians who equated that what was commonly thought of as the Western Empire, was in fact something new. I believe Notker even uses the term Europe in place of the empire as a whole.

What was the Eastern Empires reaction? Eventually they would name King Clovis I as Augustus or de facto emperor. Titles would switch hands after his death and the Merovingian dynasty would eventually give way to the Carolingian dynasty with Charles the Great who would be crowned Emperor again.

It can be argued that even with Charles people felt that they were still part of the Roman Empire, in fact even some would argue that the Roman Empire existed all they way to the end of World War II with the fall of the Third Reich (Third Republic).

So what was the reaction of Byzantium? It seemed to be someone elses problem. These were two different entities at this time, each dealing with their own problems, but still connected as seen when Justinian reconquered Italy.

Sources: Gregory of Tours: History of the Franks, Notker the Stammerer Life of Charlemagne, Undergrad in History, studied with Eric Saak (Medieval Scholar).