I noticed Terminator's video quality seemed oddly poor, so I took a closer look in emulation, and not only is it 16 color (often a fair bit less -maybe fixed palette) with heavy posterization (though it does use error diffuse dithering, it doesn't look very good regardless -and it's so coarse that it ends up looking like bad static on top of posterization)... but that's not the worst part:
It's also only 200x122 but runs at an extremely erratic update rate averaging around 6 FPS. I'm sorry to say it, but I think I've found something significantly worse than the worst cases in Rebel Assault with Terminator... (Jonny Mnemonic doesn't look much better, but it's higher resolution at least)
But even more interesting, I got thinking on Tenka Fubu again (1991 Game Arts release in Japan) and decided to look at some captures in infranview... and it turns out that it uses a similar format to Sewer Shark and Night Trap with tilmap optimized color (often >30 colors) and what seems to be lossless compression (if any -if 16 kHz audio was used, the video could be uncompressed tile frames) and rather similar dithering used as well.
The main difference from the 1992 Digital Pictures stuff is the spacial and temporal resolutions used: Sewer Shark and Night Trap used 168x104 at 15 FPS while Tenka Fubu uses 256x128 at 7.5 FPS (8 frames per update -similar to Road Avenger) which would also mean more VRAM dedicated to double buffering (not that that much matters for cutscenes).
I wonder if there's any relation to the formats SoA used or if it was simply convergent developments.