Is surface brightness constant as a function of distance? Well of course it is - the flux drops off as the square of the distance, but the solid angle subtended by the source drops off the same way, so surface brightness is constant, right?
Yet other galaxies don't have the same surface brightness as a star - if I look at Andromeda, which has a size on the sky similar to the Sun, it definitely has lower surface brightness. Yet it's made of stars. I know that in terms of (projected) surface area, Andromeda is mostly empty, with a little bit of area covered by stars, so the lower surface brightness must have to do with that, and the fact that the stars are unresolved by my eyeball.
What does the surface brightness of an object as a function of distance look like, including the transition from the object being resolved to unresolved?
 A: 
the flux drops off as the square of the distance, but the solid angle
  subtended by the source drops off the same way, so surface brightness
  is constant, right?

Right. But what happens when you can no longer resolve the source? Then the "solid angle subtended by the source" stops dropping, and only the reduced flux of the entire source can be measured. 
For astronomical bodies, individual stars are far below the resolution of the optics observing them (especially eyeballs).
If resolution were perfectly defined (that is, an unresolved point produced a perfectly uniform disk with perfectly defined edges) a receding uniformly radiating sphere, like a star, would show constant brightness as long as it was resolved, with a sharp transition to 1/$R^2$ falloff when it became unresolved - when its apparent diameter exactly equaled the resolution of the detector. Since that is not the case (see Airy Disk) the transition region is rather longer, with a more gradual transition from constant brightness which depends, among other things, on just how good the observing optics are.
In the case of the Andromeda Galaxy, your intuition is correct - there is actually a very great deal of dark space between the individual stars, and there are also dark areas caused by dust.
