While I am not 100% sure, I believe that the effect you are talking about (such as how it is seen in Command & Conquer) is a result of applying a reduced color pallet to the video. For old games, disk space was at a premium and file sizes had to be kept exceptionally small and modern advanced compression was too processor intensive to be used.
Smacker (the precursor to modern Bink video) used an 8 bit color pallet to simplify video display greatly, however this left a large restriction on the quality of video. To get around this, they allowed the color pallet to be switched out on a per-frame basis and blocks from the last frame to be used. By using each frame as a field in interlaced video, they could use a bright color pallet on one set of rows and a darker one on the other. This resulted in a dithered color pallet that was much larger than 8 bits.
Dithering is the process of using spots of color that are near a color you want someone to perceive in order to make it look like that color when the brain blends them together. The net result is video that looked much better than the technology of the day would have otherwise allowed for, which is why at the time it looked amazing, even if looking back now we end up wondering what we were on.
More detailed information is available on the Smacker Wikipedia page.