How does this alter the tribes' interactions with the Empire? Consider that, during a large chunk of the middle of the 4th century, the leadership of the Empire was all over the place, religiously.
Relativly unchanged. See, Germans actually needed an independent religiosity, would it be only for identitarian features.
Burgondians, by exemple, actually converted themselves to Nicean Christianism before converting to Arianism : while the conversion of germanic peoples to the first is really possible, as soon they enter in Romania, you'll have the appearance of distinctive features that would last more depending on their actual romanisation.
The relation with post-imperial Romanity, however, could be more smooth, especially with bishops that after all represented the urban network that romano-germans kings used for administration of their kingdom, as well as support than administrative management staff.
A quicker integration, depsite efforts of romano-germans kings (that needed a separation, would it be only to preserve a military force that was defined by its "barbarity") may be possible.
It wouldn't change many things for Franks or Burgondians, but would have interesting effects for Visigoths and Ostrogoths and most importantly Anglo-Saxons and Vandals. You may have a Gothic identity widespread to all the christian population elites appearing in the lateVI/earlyVIIth centuries instead of VIIth century.
And for Britannia, conquest may be not quicker, but certainly smoother, making it look like more as their continental counterparts; when Vandals could beneficy more easily to a stronger kingdom.
It would also strengthen the Catholic Church since they'd likely be recipients of state support.
I doubt it would be the case, at least in very significant fashion outside Africa. Visigothic treatment of Catholic clergy in Gaul wasn't especially persecuted, and actually supported the king at least partially.
Without Frankish takeover, it's generally assumed that Visigoths could have turned to Nicean credo earlier (to say nothing about Byzantine presence).
Possible adoption of more Roman laws and culture since there is less difference between the population and the new ruling class.
Southern Gallic and Italian romano-german codex were already pretty much romanized, as in integrating Theodosian codex, with the active support of roman nobility (as the Law of Burgundians, written down thanks to Syagrius).
It would have, furthermore, little impact on less romanized regions as northern Gaul or Britain.
Finally, I think you underestimate the attraction capacity of germans once most identitary barreers removed : except in some regions (southern Gaul, Italy mostly), roman elites "played Barbarians" (to quote Dumézil) using germanic names, customs, clothing, etc. as soon they can.
Rather than a more romanized romano-german world, you'd end with a quicker and more homogenic mix of roman and germans features.
That might make it harder for the barbarian Franks to conquer France since the Visigoths would be stronger,
That's indeed possible, but I'll point out it's not a given at all. Franks represented litteraly an armed people, when Visigoths seems to have been in not that higher numbers and more or less absent of northern Aquitaine.
Military strength seems to have been on Frankish side, and Visigoths didn't had much of a credit within roman population even without regarding religious problems (and, as I answered before, even a Nicean conversion wouldn't remove identitarian differences, as they were actively searched to begin with)
Would a Justinian expend so much treasure to retake Africa and Italy if they were ruled by adherents of the Nicene creed?
He would have less pretext and incitatives, critically for Africa, but his project was essentially political (I concede that religion and politics were totally mixed), as in supporting the pro-roman faction in Italy, and coming to "help" a rival visigothic claimant.
He may be more wary when it comes to conquests (accepting peace offers of Goths and leeting them a kingdom north of Po, by exemple), but would still pursue them.