Gheez! Those first 2 examples with strong midtone banding at ISO 1600 are the worst I've seen from any
body without a major exposure push. That's just nasty.
Auto Lighting Optimizer is contributing to it but if you wanted to recurve the image a little in post you'd still get the same problem.
My 5D2 used to be nearly that bad with the original 1.x.x firmware at ISO 100 to 400. It's more usable now. (love-hate that camera like I do my sometimes also very bandy 7D)
Hmmm.. the image quality we thought we'd paid for...
I don't think so.
I'd contact Canon with a complaint and send them the files they'll request. As for the red hot-pixel in the last example, it's unfortunate, but that happens on occasion. There should be a way to have it mapped out in-camera though. I don't know if the firmware will accomplish this on its own somehow or whether it needs to be done at a Canon service location.