Essentially the books have a similar approach: to use the story of one semi-mythical character to gain a wider understanding of the time and place they lived in. And they face similar challenges: a flood of artistically and ideologically embellished literature obscuring a dearth of dependable sources.
Rodrigo was retroactively incorporated into the Reconquista propaganda and 19th and 20th century Spanish-Castilian nationalism. Much of the popular image of Arthur is based on 12th century romantic literature, which by the way has strong ideological or at least moralistic overtones, as Halsall points out. This has not been improved by 20th century fantasts who have claimed to have proven certain myths based on very crude and fanciful interpretation of isolated snippets of evidence.
There are differences too: while Rodrigo can be proven to have lived and the main occurrences in his life are beyond doubt, Arthur’s best bet is that it cannot be disproven that he has existed, but that it is unclear when exactly and where. But the fundamental challenge remains to construct a narrative from very slim and unreliable evidence.
"Indeed, whether or not one of the post-imperial British kings was called Arthur is probably the least interesting question that one can ask about this important period."
Like Fletcher, Halsall is less interested in the main character than in the society that he (supposedly) lived in. Halsall effectively dismantles the 'barbarian invasion' interpretation of British medieval history. But the historical discourse which has replaced it (well presented by Robin Fleming in Britain after Rome), and focusses more on non-violent and cultural domination by relatively small groups of immigrants, also doesn't satisfy him entirely.
First of all, Halsall more strongly emphasises that Britain was not an island but part of a North Sea cultural zone where migration, like trade, was not a one-way phenomenon. This means that cultural change was not the result of conquest, but of interaction and shows parallels on the continent.
Halsall agrees with the new historiography of British decline even before the end of Roman presence and that for a long time the population of Britain saw the removal of Roman forces to the continent as temporary. Also the coming of the Saxons started as allies to the local population some time before the Roman departure. This may have been part of a civil war(s) between Roman competitors.
Finally, post-Roman Britain probably had larger political units than long assumed. Even if not strongly unified, patterns of overlordship by weak states existed, in connection to mainland Europe.
Reading Halsall it is clear that he has a very deep and keen insight into the different material available. His scientific criticism of the written sources is unparalleled and his points out many logical pitfalls in the interpretation of archeological findings. It is clear that what we can infer from them is very limited. So when he keeps open the possibility that Arthur may have really existed this is more from the viewpoint that there is no evidence to disprove his existence, just as there is no proof that he actually did. I think the book is a must read for any serious student of ancient and medieval for its state of the approach and methods.
But in the end, it's the organisation of the book where Fletcher prevails. Halsall's convoluted break up of the development of the 'historiography' of Arthur makes the book tough to finish and the part that is most interesting, Halsall's alternative view of post-Roman Britain, suffers from the reader's desire just to be done with it. Which is a shame.