I'm a bit of an optimist and think that Majorian was exactly the sort of figure the Empire needed, in terms of strong fiscal reforms in Italy that would allow a new Roman Army alongside Federates. I think to an extent that is why Ricimer killed him, he wasn't just a threat to him, but the entire system he relied on for his success.
However, he's a great PoD - you're looking at a Western Empire that is as 'Vulgar Latin' as the East is Greek, but if he'd been able to defeat the Vandals in Africa at that point, I think you've got the building blocks of a long-term restoration.
But the reality here is you're just asking to bring forward Justinians attempts by a few decades, or an incredible comeback by Nepos.
We could try and prevent Nepos being killed, and somehow overthrowing Odoacer. It isn't the most likely bargain, but you could have Nepos do Zeno a favour, and offer Theodoric and the Ostrogoths a deal - recognise and support them as eternal allies in the Carpathian basin north of the Danube, complete with offering whatever engineers are required to fortify the passes, etc, and an annual tribute for (50?) years, in exchange for their assistance in overthrowing Odoacer. Effectively a long-term alliance with the Ostrogoths. Which if accepted and successful actually leaves Nepos in a good position - the Ostrogoths being friendly and secure in OTL Hungary, and the ERE not being hostile, if not friendly, gives him secure borders if he can rebuild a fleet - and the sort of position that in the long term would allow reconquest of the rest of the Empire in time. The hard part (and the sensible action) would then be to rebuild the sense of "Roman-ness". If that means a successful African campaign, and defeating the Vandals, all the better rather than try and reconquer it all in one go.