Several notable kingdoms were situated on the island of Albion (natively, Alba) in King Arthur's time.
Britain
Britain (natively called Prydein) was a kingdom existing during the overlap between the late Roman period and the early Mediaeval period, situated in Wales and western and midlands England, with Camelot as its capital. The natively-spoken language of the kingdom was the mediaeval form of Welsh, though most spoke Latin as a common language with varying degrees of fluency.
Though nearly all of the legions had retreated back to Rome, many structures remained in use and were regularly maintained. This included military buildings, aqueducts, and bathhouses.
Dál Riata
Northwest of Camelot, there were other large kingdoms, independent of Arthur's rule and largely protected by virtue of their distance. Chief among these was Dál Riata, split into northern and southern regions by the North Channel. The south lay in Ulaidh (Ulster, Ireland) and the north lay in Alba (Argyll and Lochaber, Scotland).
The common language spoken was Old Irish, an ancient form of Gaelic that would have been nearly incomprehensible to the men of King Arthur's court, who instead spoke an ancient mode of Welsh. Much like the modern version, it is not tonal, but carries a musical, lilting quality to it, which led to suspicions of witchcraft from the more xenophobic among the Arthurian court, for those few who spoke it – very few indeed.
Although not as accomplished as the Saxon raiders, the people of Dál Riata were skilled seafarers, maintaining cultural ties across the halves of their kingdom through sea lanes. Their style of art, culture, and music were a mixture of La Tène Celtic and seafaring Scandinavian, taking elements of both and underscoring their commonalities. Indeed, many of the Dál Riata people had seafaring Saxon blood in their veins, as much as that of Ulaidh and Alba.
Some contact was maintained with Britain in the southernmost regions of Dál Riata's territories in Ulaidh, but diplomatic relations between the two kingdoms were distant. Neither kingdom trusted one another, but neither had any desire or reason to commit to open war. Trade was permitted and encouraged between the regions, as well as the other surrounding kingdoms.
In Britain, the Dál Riata were known popularly for their bards, the filídh (singular filidh), which were the local equivalent of magi. They were the keepers of lore, musicians, poets, local judges (though lesser than the brehon), magicians, and advisors to kings. Within the scope of their own kingdom, they commanded a great deal of respect; outside of it, they were regarded with fear and suspicion, much as one would regard a witch. Stories of the strange and wondrous things they were capable of burned like wildfire throughout the Isles, and the further from their home kingdom those stories travelled, the more weird and fantastical they became.
Notable Round Table characters of Dál Riata included Sir Bedivere (Fionnlagh), Sir Lucan (Ceallach), and Sir Griflet (Cathaoir). These three knights all shared blood ties, and they adopted Welsh names to better fit into Camelot's prevailing culture.
Pictland
Northeast of Britain lay the kingdom of the Picts, who inhabited most of Scotland. Many of their territories were marked by distinctive marker stones, and their warriors were known to paint themselves blue before they went into battle. Hence, they are occasionally called "the Painted People."
A proud, warrior-like culture, they were regarded warily by the Roman legions previously stationed in Albion, who built walls specifically to deter their raiding parties.
Relations between Camelot and the Picts was not openly aggressive, but there had been the occasional border skirmishes. Britons were wary of the more 'savage' people of the north, while the Picts distrusted their southern neighbours due to their ties with the Romans.
- Orkney - A petty kingdom of Pictland off the northernmost coast of Albion. The Gaels of the Dál Riata called it Insi Orc ("island of the pigs") and engaged in some non-aggressive war for influence over the kingdom, though it remained under the purview of the Picts. Notable Round Table members from Orkney include Sir Gawain, Sir Gaheris, Sir Gareth, and Sir Agravain.
East Anglia
The Kingdom of East Anglia lay to the east of Britain. (Modern-day eastern coastal England) It is a Saxon foothold from which the raiders from across the English Channel organised their battles against the Britons.