For the achives
Answering my own question for the archives:
Driver's side oxygen sensor (before cat) is easy to change after removing the aluminum heat shield above the cat. Also, there is a "clip" of sorts that must be removed that holds the sensor wire against the body. All can be done from under the car. I found that a large box wrench was best for unscrewing the sensor.
Passenger side sensor best removed from the top. Use a long extension with a oxygen sensor socket to unscrew the sensor. Its very hard to see what you're doing, so frequent trips under the car to make sure the socket is firmly seated on the sensor are necessary.