I've had a bit of time this week to work on a few stuff (actually had a day off from work, which has been nice), and decided to take a look at the video codec issue again. I've managed to convert them to the H264 codec, which does slim down the videos a bit further and puts them back on a mainstream codec. Naturally, the audio codec has remained at its default due to Outpost 2's built-in requirements (16-bit Signed PCM).
Now, the really interesting bit here is that when I switched over to Windows to play the game, Outpost 2 can't decode the videos, even though the host system can play them fine (audio plays fine though). Digging deeper, I discovered why. The built-in player is actually using the (ancient) "Video for Windows" component, which is why I haven't managed to switch over to a codec that doesn't require us to install something extra. That said, it's still an improvement over FFDShow, and there is a Video for Windows version of the H264 codec, so I figured I'd share with all of you anyway.
I do want to point out that during my attempts to grab a fresh copy of the videos from the download page, I noticed that the link is actually broken. It points to outpost2.com instead of outpost2.net. Simple enough to fix, but casual people interesting in starting out may not think to do that.
H264 Encoded Videos Download:
https://sam-node.com/nexus/index.php/s/T4MDTCjQmbizRgL/downloadVfW H264 Codec:
https://sourceforge.net/projects/x264vfw/Edit: I've also gone ahead and updated the Wiki with this new information.