Sadly, there isn't enough information in your post to provide you with a conclusive answer. However, the following should help to illuminate some of your issues.
Background
When you are rendering to a codec, the codec shifts the color encoding scheme from RGB to another format typically. In most instances this is a YCbCr schema, which provides one channel for luminance, and two channels to describe the color, or chromaticity, of the pixel value.
Most codecs are designed for low bandwidth and small file sizes. In order to achieve this, they will compress and scale portions of the data to make the result fit into the designed constraints. Within the realm of YCbCr, our visual systems have learned to pay more attention to luminance over chrominance. In codecs where data size is an issue, engineers leverage this perceptual trick and more greatly compress the chrominance, or the Cb and Cr planes, as compared to the luminance plane, or Y.
Knowing that typically all three planes are compressed in a codec, and coupling that with understanding that the Cb and Cr planes are even more greatly compressed, we can begin to understand why posterization occurs in encoded formats. The more greatly compressed the stream, the greater degree of posterization.
Ultimately, even when given a well encoded RGB image at eight bits per channel, an encoded motion picture format will more often than not degrade this acceptable level of encoding to a point where it may be unacceptable given some contexts. Gradients are one example that will exacerbate this phenomena.
So how to avoid posterization? The most ideal way is to encode to an uncompressed RGB display referred still image format, and then leverage an external encoding tool that permits you to control the YCbCr stream details. With a decent set of encoding parameters including bitrate and compression level, you should be able to pull the posterization into acceptable levels for eight bit motion picture presentations.
Enough of that, what damn codec?
So even if someone is telling you to try a "lossless" encode, while it will try to maintain accuracy, will still include a conversion to YCbCr and likely some scaling at the very least, which will not be lossless when comparing to the source RGB format. If you use a codec that remains in the RGB domain, you are avoiding one transformation, but even then, you will be likely quantizing your image.
Remember too that not all codecs may be decoded at all or correctly when your content arrives at the destination you choose, so use caution. This includes middle layer services such as YouTube, Vimeo, etc., that will more than likely re-encode your material yet again, subject to another entire set of mistakes and encoding problems.
With the above caveats, the following options direct out of Blender will likely be closer to what you were hoping:
- HuffYUV. HuffYUV can deliver both YCbCr and RGB formats. I actually patched this portion of the code to remain in the RGB domain and as such, it will be closer to what you are seeing in the 8 bit display buffer output from Blender.
- FFv1 will be a lossless encode, with the above caveats of YCbCr transforms and quantization. Test to be sure.
- H264 lossless should be a losseless encode, with the above caveats of YCbCr transforms and quantization. Test to be sure.
If anyone would like help on how to test if an encode went correctly, it would be useful if a new question was posted. This would allow for a proper response.