Spain already required heavy reliance on Berbers with Arabs being a tiny minority during the conquest.
That said, Romans didn't had a really important presence west of Africa : their presence in Spain was mostly about preventing Goths to meddle on west Mediterranean Sea (and a bit of an opportunist strike, dealing with the usual uneasy gothic succession), which was essentially restricted to the coast (Cordoba's region and Orospeda may have been more semi-allies than part of the province) and relatively low on the list of priorities.
Fair enough, Romans didn't depended on Berber for control of the region, but it have a lot to do with Berber chiefdoms entering a phase of contraction which ceased at the coming of Arabs : it's partially due to Byzantine conquest of Africa (that had for main result to push back Bebers as a "foreign" people and peripherize them) and probably the Justinian plague as well. Visigoths didn't had that of a problem taking back the Roman-held coast, IOTL.
So, for what matter westernmost Mediteranan basin, I think Romans would stick it to their traditional policy (at least for the forseeable part of the TL) of war by proxy and subsides policy; because they didn't have the local manpower that Islamic West had in the region (even if the latter was mostly autonomous on several matters, significantly more IMO, that what preceded exarchates)
This lead to exacerbated ethnic strife which lead to the taifas in the long run, and the Berber Revolt in the short run.
For what mattered the Berber Revolt, it's not just an andalusian happenance : it's due to the generalized bad treatment of Berbers in all the Islamic West, especially by the wali of Ifriqiya (which held some sort of vice-royalty equivalent over the western provinces, mostly held by the Fihird dynasty), with Berber being treated as Islamized peoples, or as non-Islamized peoples whenever it was most convenient (basically, the first when raising taxes due by Muslims and military services; the second when raising taxes due by non-Muslims, enslavement, and generalized humiliating decisions).
The first outbursts did happened in Spain, mostly because Berbers were settled on the frontline, in relatively poor but remote lands, enough to allow mutinies to take places (with probable support from Christians, such as Munusa did in Cerdagne with Aquitain support); but it's an answer to a situation pervasive to the whole of Islamic West, where "Arabism" was more marked than in other regions (and why Arabo-Andalusians eventually went with making Abd al-Rahman their emir, as Umayyads were seen as champions of Arabity)
It more or less led eventually to a difficult ethno-politic situation (which led to Muladi revotls during a good part of the late IXth and Xth century), and while it less expains why taifas were established, it does provides an explanation how they were established.
While Berbers were generally arabized (especially in the core regions or urban centers), you even had another differenciation between
Andalusian Berbers, settled since the early part of andalusian history, and African Berbers (mostly settled since the late IXth, and more usually in the southern regions), with of course the tribal affiliations.
But I digress : the point, when it comes to the OP, is that the Caliphal functioning but as well institutions implied in its early history that it had to expend; which wasn't the case of Romania which was more built on strategical concerns after the half-butchered conquest of Africa, mostly because it could fund endless expensions and wasn't going to allow semi-independent campaignins as Rashidun or Umayyad caliphs did (even if the history of Roman Spain or Exrchate of Carthage points that you could end pretty easily with neglected regions).
Berbers for, Arabs, were a vital military force when it came to raids (in Maghrib, then Andalus and Gaul); while they were for Byzantines either a convenient suppletive force, or a peripherised hinderance, depending of the situation.
The question is less how Byzantines could have pulled a similar use of Berbers that Arabs did (as it would have implied a complete change of strategical and imperial perspective), than how
Berbers chiefdoms (being understood you had a lot of Mauri communities and foedi inside Byzantine Africa, not represented there) are going to evolve ITTL after the aformentioned period of contraction, with a Romania fairly uninterested on them, but while unable to crush them, unwilling to see them grew too much outside their scope (not to say that they could really do something about this, would opportunities arise)