Lots of love for Bink, but Bink's predecessor is an earlier video codec/format called Smacker, which was especially for 8-bit colour palettes, where the palette (or part of it) might be fixed due to being needed by UI elements outside the video, but some or all of it may be allowed to vary/rotate as the video played.
I first encountered Smacker videos in Caesar II (which even shipped smkplay.exe on the disc so you could play them from outside the game), but they were used for a lot of games of that era, including a bunch of early Blizzard titles like Warcraft 2 and StarCraft.
I immediately thought of Caesar II when you mentioned Smacker :). One of the impressive things in that game (besides being a great game) was the many very smooth video clips, enabled by that tech.
I first encountered Smacker videos in Caesar II (which even shipped smkplay.exe on the disc so you could play them from outside the game), but they were used for a lot of games of that era, including a bunch of early Blizzard titles like Warcraft 2 and StarCraft.