Well, got a check engine light yesterday in my 1996 S500 Coupe. I pulled the code from the ODB-II system and got a PO150, which is the forward oxygen sensor on the number 2 bank. The car's got a little over 80K miles on it, so not terribly surprising.
Anyway, crawled under today to scope the job... the passenger side O2 sensor is in an awkward place, but looks reasonable. The electrical connector is clipped into a holder of sorts on the side of the trans. No sweat.
The driver's side is something else... the sensor is accessible, but the electrical lead immediately disappears between the body and a large heat shield for the cat on that side. The shield is attached to the body in such a manner that its impossible to see where the lead goes. There is virtually no room between the body and the shield.
Maybe somebody who has done this job on an mid 90's S500 can give me some clues... do the heat shields on the driver's side have to come out? Is that the only way to access the electrical connector? Where is it? Tricks, hints, prayers?????
Thanks, KenP

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.
KenP