The present application is directed to techniques and tools for adapting the quantizer as well as the quantization step size used during video encoding. For example, a video encoder uses a non-uniform quantizer (having a relatively large dead zone ratio) for B-picture types, but uses a uniform quantizer for other types of pictures. In many encoding scenarios, this helps the encoder control bit rate for the B-picture types instead of resorting to higher quantization step sizes, which improves overall quality for the B-picture types.