Let's say that Majorian manages to conquer the Vandals and keep Ricimer and his faction loyal (or deals with them in some other way).
He goes on to rule the empire for around 20 years subjugating the Franks and reestablishing the Rhine border as well as grooming a capable heir. Lets assume that this leads to a century or more of relative stability in the empire which manages to recover somewhat.
At this point, things already went too far for being really reversed in WRE : Majorian managed to put foedi into obedience, and would have he managed to defeat Vandals, it would in all likeness turned the same : putting them back to their original foedus (in this case, Numidia) and at the first crisis, Barbarians would have returned to their usual policy of negotiating in a position of strength that Ravenna couldn't have really curbed down. At best, we're talking of Constantinople assuming the contol of Africa and Italy, which is arguably a huge change. But WRE was done for : it depended too much from either Barbarians or Constantinople to remain independent.
(In addition, the problem of Ricimer was not his lack of loyalty,
but being much more bent on preserving what was possible of WRE from Italy even if it did mean giving up on provinces, which wasn't a goal on itself as the expeditions of 460's point)
If you want a surviving WRE, you'd really need a much earlier PoD that would prevent at least part of the damaging crises of the Vth, probably no later than the 430's, probably earlier if you want to butterfly away the Hunnic hegemony and its consequences.
Will it become more feudal in character (especially considering the many federate tribes within its borders)?
As feudality, understood as the fusion of beneficii and honores (roughly, making public land and nobiliar power indistinguishable) appeared only with the rise of Peppinds/Carolingians, I think it's safe to assume it wouldn't appear as such.
If you meant, however, a greater regionalisation, socially or politically-wise, it's likely to have something still emerging especially with permanence of foedi but elsewhere in Romania too : still, the permanence of an imperial figure would probably make these regional ensemble more tied together, not unlike the situation you eventually ended up in Gaul.
Will urbanization still decline?
It's really debatable if the urbanization in the VIth century was significantly declining relatively to the Vth century : most of the damaging effects on this regard happened in the IIIrd century (especially in Western Romania, were a city was less defined by its population than its basic structures). More importantly damaging was the decline of the urban middle-class that lived from the existence of a same political-economical structure, and that was disappearing in the VIth due to the ongoing trade decline.
What would the empire's relationship be with the germanic barbarians?
In the Vth, considering Barbarians as Germans is more an ethnicized pseudo-history than really accurate : materially and politically, we're talking Romanized populations growingly made up of bona-fide Romans.
Depending on the PoD, we're talking more or less powerful foedi and mercenaries, : if we consider something roughly comparable to IOTL, they would act as a double regional hierarchy with the Roman state, rather than something really subordinated. It's hard to give a comparison giving the relative originality of the structure, but consider these as a vassalized independent states who would still be dependent on their relation with Romans.
Something comparable to the relations Constantinople had with Barbarians IMO, meaning sending prestigious gifts (such as silk) but more importantly gold (generally coined locally) and subsides. Giving that Barbarian princes tended to consider negotiations and treaties passed by the emperor more as a personal agreement than something tied to the Roman state, it would mean WREmperors would still have to regularly fight back or to renegotiate. Giving that WRE was extremely dependent on either Constantinople (that would be too busy in the East to really be helpful continuously) and foedi to raise armies, they wouldn't be able to get rid of them.
(Of course, if you still consider a Majorian PoD, then we're talking of a sole Roman Empire that would likely have absorbed Africa and Italy, letting Spain and Gaul as foedi, but that's another debate).
Will they become more or less of a threat as they convert to christianity (If they even do)? Will they be more likely to become Niceans rather than Arians ITTL?
Two things there.
They weren't as much an existential threat (they became such because WRE became a failed state after the 430's) than an inner threat due to their powerful position in the Roman military militia and chain of command, and the reliance of Romans on their foedi and mercenaries as both police and army.
Without talking about a symbiotic relationship, we'd be rather considering a twinned state if you allow me the expression : and more Barbarians would be integrated into Roman institutions, more likely that in a time of constant crisis, they could rise higher.
As for Christianity, by the 430's, Barbarians were as said above, essentially Romanized which means they were mostly Christianized. Homeanism was dominant at first because Barbarians played lip service to the emperor by abiding to his own belief, and they kept it (even switched from Nicean credo to Homean for what matter Suevi and Burgundians) as it allowed them to mark a distinct identity in a period they basically looked and sounded like Romans.
ITTL, I could see Barbarians remaining Homeans longer than IOTL, everyone benefiting from having a marked distinction between romanized Barbarians and Romans; but at term the sheer gravity of Niceanism and the fusion of Barbarian and Roman elites would lead to at least a mainly Nicean dominance.
As an aside, I use Homeanism rather than Arianism, because you have important differences : roughly speaking the first is a semi-Arianism which "only" subordinated the Son to the Father while Arius considered only the Father as divine. Homeanism also is not really dogmatically defined and seems to have actively prevented really going in detail about what made the divinity or not (contrary to what happened with eastern Christology) arguing that it was insane to claim grasping divinity : it eventually allowed it to pass as close enough to Niceanism, and to not implode into various sub-beliefs.
What would be the relationship between church and state? Will it be similar to the relationship between the Holy Roman Emperors and the pope IOTL or will it be more like in the eastern empire?
It would not look like what happened in HRE at all, of course : Rome had centuries to emerge as an independent institutions and defining itself as a prominent power (which is arguably a consequence of Ottonian intervention), which wouldn't happen there.
I don't thi it would be entirely comparable to Constantinople, even if it would be closer : EREmperors had to deal until the VIIth with various patriarchates and propelled Constantinople to impose their religious policies all the easier (especially when the empire lost Alexandria, Jerusalem and Antioch)
In a surviving WRE, there would be only one big seat to deal with, its probable moral and pastoral prominence not being put in question, so I guess a relatively smoother (for the emperors) relations, and no quasi-federation of royal churches as it appeared in the Early Middle Ages IOTL. Definitely something more imperially driven, although the religious unicity wouldn't make the pope a mere figurehead.