But, taking not too much poetic license, we can argue that human society at a whole is a 10^6m scale intelligence (well, more like 10^3 if we are only counting the pile of human brains, but the distances are still in the 10^6 scale). It furthermore has incredibly slow thought transmission outside of very small "fast" nodes. Yet it solves the problem by not requiring most signals to propagate very far. Only a few ideas need to be globally known by humankind, the intermediate filtering is still mostly local.
So, a galaxy-sized "brain" can exist, it just needs to be very hierarchical, since any global consensus would take hundreds of thousands of years to formulate, even at the speed of light. In computing / distributed system terms: locality matters.