> 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.