Definitely I think Arthur would've succeeded his uncle in this case, his being underage seems to have been the only reason Richard skipped him over IRL. Richard actually already named him heir upon leaving for the Third Crusade, and only changed his mind on his deathbed b/c he obviously didn't foresee dying of a gangrenous crossbow wound at that time. Meanwhile John already allied with Philip Augustus of France to overthrow Richard (but failed) while the latter was stuck in a German prison - that attempted usurpation being the time period in which the Robin Hood legend is set. In general the Plantagenets were a pretty fractious bunch prone to self-destructive infighting, but this seems to have been more true of Henry II and his family than any other generation of that family until the Wars of the Roses; there seems to have been little to no love lost between Richard, his brothers and their father.
IIRC Arthur was supported by the continental barons of the Angevin Empire while John had the backing of the English nobility (and then proceeded to piss the continentals off even more after he secured his crown by doing things like stealing their betrothed for himself, as with Isabella of Angouleme), so we might see the Plantagenets being able to hang on to their mainland holdings for a bit longer. But the Capets were getting much stronger as of the early 13th century so unless the longer-lived Richard or Arthur manage to turn
Bouvines or a similar battle into a crippling blow for them, they'll probably still succeed in eroding the Angevin Empire, just more slowly. IRL Philip supported Arthur against John not because of any great affection for the boy but for the purpose of weakening England, just as he had backed John against Richard before; ITL I imagine he'd just help John against Arthur for the same reason.
Assuming an Anglo-French war in the late 1200s or 1210s, I could see John helping Philip take over Normandy and causing trouble in England while Arthur fights with the support of whatever English dudes he's managed to gain the support of with his extra ~10 years of life/rule & Richard's backing (William Marshal for example would join him ITL I believe, he seems to have been a Lionheart loyalist above all historically and only joined John b/c Richard had named him the heir at last minute - indeed he ended up helping to fight
against John earlier when he betrayed Richard, comes to mind as a more successful prior incarnation of the Roses-era Baron Hastings) and his own Brittany. Plus the HRE (led by Otto IV of the Welf dynasty, his cousin) and the various Angevin/Poitevin/Occitan barons, including the powerful Lusignan clan who were historically his champions.
On the balance I think the English can get away with 'just' losing Normandy if they're defeated in this scenario - John does not strike me as a leader capable of wresting the crown from his nephew while starting at a pretty disadvantageous position and without the help of vastly more talented & likable lieutenants like Marshal. If Arthur still has to agree to the Magna Carta or something like it, it'll probably be to definitively win the allegiance of the pro-John English nobility this time around, perhaps at Marshal's instigation since he was one of its big backers IRL. Arthur also has the additional advantage of having two very attractive hands in marriage to offer leading up to or during the war in order to create new alliances, his own & that of his sister Eleanor the Fair Maid.
