Here is a picture I took of the front HO2 sensor when I had the cradle out to stud the engine. The diagonal orange jack handle running diagonally at lower left is just below the sensor which is about midway up the jack handle. The aluminum block with the puddles of antifreeze is the ABS block. You can see from the top I think but if I recall you have to remove the air cleaner box and probably push the long radiator hose out of the way. Anyway, the ABS block is one the front driver side corner of the cradle so the sensor will be a little towards the center of the car above the front cradle cross bar. From underneath it looks to be above the point where the aluminum power steering return line crosses over the front cradle cross bar on the driver's side. Be aware that you are going to have AC lines, radiator fans, transmission connector, cradle cross member and numerous cables trying to occupy the same space as your hand when doing this, it will not be as accessible as it looks here.
Also, before you do all this, I would suggest you check the connector to the PCM (located inside the air cleaner box for cooling purposes) and the sensor pigtail to make sure that the connections are secure and undamaged. I would reseat the connectors on the pcm. Also, look for frayed wires from the sensor until they disappear into a wire bundle. The heater is controlled and monitored by the PCM.
Here is a close up of the sensor, I believe it is a 22mm socket or wrench. Be careful not to touch the business end (sensing bulb) when installing/handling the sensor. Don't forget to torque it if you can get a torque wrench in there. I did all 3 of my sensors while the cradle was in front of the car on jackstands, considerably easier than that which you are about to embark upon. Courage matey, there may be scraped knuckles and child inappropriate language ahead but you'll get it done. Before you embark on this I received a private message from Submariner409 that he would think about it and reply on this thread. I told him I wasn't certain I was on the right track (cat converter), you might want to give him a day or so to chime in. If you don't have the torque value I will try to look it up for you later today.
I think this is probably a 1 1/2 six pack difficulty level job when done in the car. May I recommend Heineken?