> Doesn't there have to be some reference frame whereby a body is not moving through space at all?

Relative to what? If you're measuring against the expansion of the universe, then you'd have to take VERY precise measurements against the most distant objects, and they're moving in all kinds of directions, but if you could, then sure, you could do that, somehow.

You'd just be moving at an insanely high velocity relative to anything local to you.

And because you're moving at that insane speed relative to, say, earth, you'd have to apply a massive force to actually get up to that insane speed.

> But if all speed is relative, both should see the other speed up, which feels paradoxical.

Welcome to relativity. Say you have 2 objects approaching Earth at 0.1c, relative to Earth. They'd see each other as moving less than 0.2c, because it's not additive, and if they could each see a clock on the other ship, they'd see that clock moving slower than their own.

> Under the laws of special relativity an observer in a space ship travelling at 0.1c will see Earth speed up, while an observer on Earth will see the ship slow down.

No they won't. They'll both see each other slow down, since motion is truly relative. From the perspective of the Earth, the ship is moving away. From the perspective of the ship, the Earth is moving away. Neither is right or wrong. Both see symmetrical time dilation.

The unintuitiveness of this fact is why the twin paradox is so famous, despite not really being a paradox: https://en.wikipedia.org/wiki/Twin_paradox