Part 3a: Dust and Explosions
To a first approximation, there's exactly one thing that sets the speed limit on going fast in space.
In the future, dust will be a Very Big Deal, as it's the dominant constraint on the most-important instrumental goal of going fast.
Anders Sandberg's paper pointed out dust as a constraint on interstellar probe design, but I didn't realize exactly how huge of an obstacle dust was until I started playing around with a spreadsheet.
To start with, interstellar (and intergalactic) dust has a size distribution, which tells you, for a given diameter range, how many dust grains there are of that diameter in a given volume.
At least for the range of 35-120 nanometers, (which shows up especially strongly in astronomical observations) it follows a power-law distribution, with an exponent of -3.5.
However, this dust isn't what we're worried about. There's erosion from protons and small dust hitting your dust shield at relativistic speeds, but doubling the dust diameter means it's 8x as massive and hits with 8x the energy.
At 0.9 c, 180 nm dust hits with 1 joule of energy. So all the normal dust isn't that much of an issue.
Going up to dust that's 1 micrometer wide, it hits with about 100 joules of energy, the energy of a firecracker. For all the following explosion comparisions, note that it's going to take the form of a super-narrow pinprick of kinetic energy directed on a single point, which is more destructive than a simple explosion, which radiates in all directions and has much of its energy dissipated as heat.
Destructive power keeps scaling rapidly, with about a factor-of-ten increase for every doubling in dust diameter, until we reach 20 micrometer dust, which hits with the energy of a grenade.
40 micrometer dust hits with the energy of 1.5 kg of dynamite. 86 micrometer dust hits with the energy of 30 bricks of C4. 0.18 mm dust hits with the energy of half a cruise missile. 0.4 mm dust hits with the energy of the Oklahoma city bombing. 0.86 mm dust hits with the energy of the largest non-nuclear weapon, the Russian FOAB. 8.6 mm dust hits with the energy of the Fat Man nuclear weapon, and 1.8 cm dust (a ball bearing) hits with the energy of a W87 fission warhead.
So, from about 1 to 20 micrometers, we get a pretty decent amount of boom that's shieldable. Whipple shields are the current standard for micrometeor impact. They have a protective thin layer that gets hit, turning the blast into a cone of shield-vapor, and then the force of the blast is dissipated over the area of a cross-section of the cone on the main bulk of the ship, which is much more manageable. However, I'm pretty sure that at relativistic speeds, the cone gets a lot more narrow, so they get less effective.
20 micrometers to about .1 mm is handleable if your ship is really damn sturdy.
.1 mm to 1 mm requires increasingly large dust shields that will start looking more asteroid-like, getting bigger than the mass of the rest of the ship, as they have to be that big to tank a hit from the largest non-nuclear weapon focused in a single tiny pinprick and narrow cone. Remember, by relativity, there's no difference between cruising through the interstellar medium at 0.9 c and being in the beam dump of a particle accelerator that's whipping stuff up to 0.9 c. Anything larger than 1 mm requires that most of the mass of the mission is composed of an asteroid, with the size of the asteroid rapidly scaling with dust size.
So, up to about 10 micrometers, we need a decent dust shield, 10 micrometers to 0.2 mm requires the sort of dust shield that can tank a hit from a cruise missile focused in a single point, and beyond that we basically have to whip an asteroid up to 0.9 c and attach a small ship to it with very rapidly scaling asteroid size. This requires quantities of energy that could blow the crust off a planet.
We know a lot about low-diameter dust that can be conventionally shielded with little issue, but we know very little about the distribution of higher-diameter dust, and that's the dominant constraint on mission speed and colonizing the universe. Of course, if we get a really bad distribution of higher-diameter dust, we can always go slower. For non-relativistic speeds, halving the velocity cuts the impact energy by a factor of 4, and for relativistic speeds, you get a lot more than that because of decreases in the relativistic-mass of the dust grain.
Maybe we'll get lucky and find that there's a sharp dust-grain cutoff beyond a certain size. Maybe we'll get unlucky.
Part 3b: Dust Distribution Facts and Implications
There are three relevant considerations I found, trying to work it out from first principles and astronomy facts. The first is that a dust size distribution implies a certain amount mass in a volume of space by doing the appropriate integral over diameter. The -3.5 exponent means that the amount of mass diverges. In order for the integral to converge and have finite dust mass in the universe, you need an exponent a hair below -4. But we don't know the diameter where the exponent shifts down to -4 or lower.
The second is that the asteroid belt has a size distribution of -3.5, and this is apparently characteristic of fragmentation processes. The reason there isn't infinite mass in the asteroid belt is because there's a size cutoff at the mass of Ceres. And we get the intuitive result that the mass of the asteroid belt is mostly in large asteroids.
The third consideration is that dust comes from many processes. Supernovae and dying stars floof out a bunch of dust into the environment. We found a supernova grain as large as 25 micrometers once, which is worrying. But most supernova dust is a lot smaller than that. For the millimeter-size dust grains, I imagine it'd come from planetary formation discs that got disrupted, which is a different process with a different dust production rate. So I'd expect different regions of space to have different dust size distributions, some of which might come with a natural mass cutoff. Maybe molecular clouds with forming stars are especially dangerous. Maybe the void between galaxies is mostly devoid of fatal dust (relative to the hydrogen density). Maybe dust gets more and more abundant as a galaxy ages so it's much more dangerous to travel in distant galaxies that have aged by the time we get there. We don't know, but it's probably modelable.
Now, there's two more things to note.
The first is that required-asteroid-mass to shield against the largest dust grain likely to be encountered is ridiculously sensitive to the scaling exponent, and pretty sensitive to how fast you're going. Pretty much, if you make your asteroid have twice the radius, you get 8x the mass, so you can tank 8x larger explosions, right? Well, maybe tankable explosion power doesn't scale linearly with mass, I'm unsure. But more importantly, your asteroid now sweeps out 4x the area because it has 4x the area, so you're 4x more likely to hit dust of a given size. Now, overall, you're still better off, but an increase in mass doesn't buy you nearly as much dust protection power as you'd naively assume, so dust still sets a pretty hard speed limit with quite rapidly scaling asteroid mass for traveling longer distances and higher velocities.
The second is that, due to the fact that dust is the dominant obstacle to going really fast, there will be an awful lot of optimization power directed at this problem, so the standard caveats apply about concluding that even a transhuman civilization can't do high-speed missions due to dust. Two obvious improvements I can see are making materials that are really good at dissipating massive pinpoint kinetic energy strikes, and finding some way to deflect dust. I think there's ways of charging the dust ahead of you and using a magnetic field to move it out of your way, but it's hard because we're mostly interested in large dust which is a lot less susceptible to these shenanigans, though I'd have to check. Also, any dust deflection system (and the power drain imposed by it) must be running full-time over the intergalactic voyage, which brings in the standard problems about making machinery that long-lasting.
Edit: In the three hours since typing this, I found that someone invented a completely novel deflection strategy I missed, and I also invented another one on the spot, proving my "don't underestimate the future" point very well. The one I didn't come up with is throwing a bunch of liquid metal droplets ahead of your ship, enough to ensure that a dust grain hits at least one of them and explodes, like an extremely long-distance whipple shield and very slightly accelerating the whole way so you can recapture the droplets and launch them back ahead of you. This has the issue of requiring continuous acceleration, and losing mass the whole way due to cosmic ray spallation of the droplets, and droplet vaporization when they get hit by smaller dust grains. Off the top of my head, it'd be pretty decent for an in-galaxy mission, but I worry that for intergalactic missions, the cumulative mass loss from droplets getting destroyed, and the propellant/continuous engine operation required to continuously accelerate the whole way, would be a bit much, plus it doesn't work on deceleration, just coasting. No, I'm not going to redo my design from scratch to take this into account, it's eaten enough time already. As for my insight, it's that if you have many spacecraft in a line, each can protect the next one, so the volume of space swept out by the fleet is much lower. Or, heck, you can just have the first dozen in the train being inert blocks of rock and only build important attachments for the stuff in the back.
So, for my mission, I assumed we're just directly tanking the impacts on a giant block of graphite, and there's a dust scaling exponent of -5 in intergalactic space (there are less protoplanetary discs which is where I think a lot of the scary dust comes from, and there aren't a lot there), a scaling exponent of -4 in interstellar space, and -3.5 closer to a star. As an example, shifting the dust scaling exponent of intergalactic space to -4.5 increases the mass of the asteroid we have to send by about 3.4 million times. This is what I meant by mass being ridiculously sensitive to scaling exponent size. The resulting dust shield mass per supercluster-ship (mostly dust shield though) is about 120,000 tons for a squat cylinder of graphite 42 m or about 140 feet long , or about 1/5th the mass of the titanic. Also we'll need about 30 of these for a 99.9% chance that at least one survives (higher survival probabilities are attainable by just sending more) It's far more efficient on a mass basis to send a fair few ships with a moderate chance of survival than to send one big ship with a 99.9% survival chance.
So in summary, dust size is the dominant constraint by far on how fast you can go, with unacceptably rapid-scaling mass increases as the exponent on the power law goes up.
Edit: Unless transhuman or mere-human ingenuity comes up with a way to cheat some part of the dust problem, in which case we're back in business.