At least on stairs, I think this is a solvable problem: https://www.technologyreview.com/s/601240/an-impressive-walk...

In terms of off-the-shelf: http://makezine.com/2015/05/01/meet-stair-bear-adorable-clim...

I also vaguely recall seeing some demos of first responder robots and stairs. I don't know about the other issues you've raised...