Originally smooth unicolor background shows "steps" in the color gradient when exporting
The choice of codec will largely depend on what you're doing with the material. Your problem is that there just aren't enough colours in 8-bit colour space to give you a smooth gradient over the size of the frame.

Problem is that if you want to deliver it on the internet you're pretty much locked in to h.264 (or I guess webm or ogv, but same deal). You can encode h.264 in 10 bit, but almost no-one will be able to watch it, and certainly not in a browser.

There is a workaround which can help a little, which is to add some noise to your gradient. What this does is to break up the banding so that it's not as obvious. It's called dithering, it was big when 256 colour gifs ruled the earth. See this answer for a bit more detail.