This suggestion may be controversial: os.putenv should decode bytes arguments as UTF-8, the new Windows filesystem encoding. Moreover, os.environb should also be implemented. This would be consistent with bytes support in os.spawnve and os.execve.
The controversial aspect, I think, is that this doesn't allow using arbitrary encodings for environment-variable names and values. The statement in the docs that os.environb allows one "to use a different encoding" than the filesystem encoding would have to be modified with a caveat that on wide-character platforms, such as Windows, using the filesystem encoding is mandatory.