I would like to say that however that Brythonic and Gaulish are (or more properly, were) closer. "Old Brythonic" (the language spoken in Britain in Antiquity, which was the ancestor language of Breton, Cornish and Welsh) did have innovations in common with Gaulish which are not found in the Goidelic languages:
- The *Kw to *P shift is one feature, but since this also occured in Osco-Umbrian and Greek, you might argue that this occured in Brythonic after Gaulish and Brythonic split. However, there are other features, which is why I cannot get tired to say that the Q-Celtic/P-Celtic division is a simplification, and Gaulish and Brythonic have more in common than being P-Celtic. I agree though that this shift most probably goes hand-in-hand with the Hallstatt/La-Tene period.
- The shift from *nm- to *nw-. This is found in the word for 'name': it's "Anwana" in Gaulish, "Enw" in Welsh and "Anw" in Breton. In contrast, it's "Ainm" in Irish and Scots Gaelic, which is closer to what would have been the proto-Celtic form ("Anmana" - compare English/German "Name", Latin "Nomen").
- Brythonic and Gaulish have a shift from *ml and *mr to *bl and *br, respectively. It is true that the Goidelic languages also made such an innovation, but at a later point: Old Irish still had the original (Proto-Celtic) condition in respect for this sound law, whereas the shift only occured in Middle Irish (the actual ancestor language of modern Irish, Manx Gaelic and Scots Gaelic). Examples for this sound law would be:
Gaulish/Galatian "Brogos", Welsh/Breton "Bro", but Old Irish "Mruig".
Another example would be Welsh "Brad", Breton "Breud", Gaulish "Bratu", but Old Irish "Mrath". A non-Celtic cognate for comparison would be Greek "Martys" (witness, or 'martyr', which is where the English word derives from).
A third example would be Gaulish "Blaton", Breton "Bleud", Welsh "Blawd" but Old Irish "Mleith". For a non-Celtic cognate (to show that Old Irish was closer to the original) compare with German "Mehl" (flour).
So as you can see, there's a number of sound laws in Gaulish and Brythonic that are/were absent in Goidelic. An interesting aspect here is that ancient Goidelic (even Archaic Irish, as found in the Ogham inscriptions 4th through 6th century AD) was fairly close to Proto-Celtic, even closer than Gaulish.
You brought up a very good point about the sprachbund in the early Christian period. In my opinion, this is where most of the so-called "Insular Celtic" features (found in Goidelic and Brythonic, but absent in other branches of Celtic) come from, in particular, making away with the elaborate declension system that the 'Continental' Celtic languages have in common with other old Indo-European languages such as Latin, Greek and Sanskrit.