Every cut scene I load eventually halts and overlays square bits from multiple frames. Intros, outros and colonization scenes are almost unwatchable from this.

Reproducability: Inevitable, invariable, has occurred on multiple computers.

Fix your codecs?

Sounds like a problem with the hardware, I had that on my old computer, on the new one with way better specs I did not get the same issue.

He mentioned he can see this on multiple computers, so I assume it's not a hardware issue, but a software one. Like when you install those old garbage codec packs, like k-lite, that mess up your system so it can't use proper codec anymore.

I replaced the codec, that did nothing to fix playing it in game. Directly using media player applications on the mp4s had much less trouble. From what I tried only the Cravers intro suffered, and even those errors disppeared when switching to Windows Media Player Classic.

That's because MPC uses its own internal codecs (LAV filters). I'd suggest to try remove 3rd party codecs, instead of replacing them. Windows 10 also ships with codecs in system already for most modern formats, so you usually need to instal external codecs only when dealing with video editing.