Pangur Bán
Deconstructed
Actually, Robert the Bruce was of partial Gaelic ancestry, he simply happened to have Anglo-Norman paternal ancestors; common practice was for Anglo-Norman lords to marry daughters of the Gaelic aristocracy to cement relations with the indigenous power-structure. By that time, the Lowland nobility was a pretty thorough jumble of Gaelic, Anglo-Norman and English- Wallace's compatriot Andrew Moray, for example, had similarly mixed ancestry, but traced his paternal ancestry through a Gaelic noble house- but many identified as Gaels or Scots (at the time synonymous), and would've spoken fluent Gaelic, it being the court language of the time.
Granted, yes, Bruce may not be considered to be of pure Gaelic ancestry, but in a game with Macedonians in Greece, Germans in England and Corsicans as French, it's far from the most blatant inaccuracy.
You are right about Robert. Robert was as much a descendant of Fergus of Galloway as the Bruces of France. He was quite at home in the Gaelic lands of Carrick and Argyl, and in the English lands of Annandale, and among the French elite of Britain.
Actually, the court language switched to English during the reign of Malcolm Canmore and the power center of Scotland moved south to the lowlands. Gaelic was well into it's decline by the reign of the Bruce.
Although this is frequently stated, this is a myth. It is a myth in that there is no evidence for it, and in that it probably isn't true. The first detailed evidence for the composition and cultural makeup of the Scottish court comes from the writings of Ailred of Rievaulx. Ailred makes it clear that one half was "us" [i.e. the Anglo-Normans], who are clearly newcomers, and the other half "the Scots". This is the second decade of the 12th century.
Also, there was no concept as "Lowlands" in this era, nor for centuries to come. People in the 12th and 13th centuries however did distinguish "Scotland" [the area north of the Forth] and "Lothian" [roughly, Lothian and Borders]. There was also Galloway, which wasn't really part of the kingdom until the era of Robert's granddad.
Brian Boru strikes me as a better Gaelic nation builder too. My Scottish ancestry wants a Scottish Gaelic leader though How about Kenneth MacAlpine?
I've often pushed for a Gaelic civilization in the past, though it is a tough one as there is such a clear division between Scotland and Ireland, it may very well just be better to accept one.
I don't think either of these leaders are good candidates for a united Gaelic civ. Brian Boru is too Irish, and Cinaed is too Scottish [probably a Pict too]. Maybe a legendary leader like Niall Noígíallach? Or a religious one, like Columba?