I just did this, go to Auto Zone and rent the special tool designed to remove the Ford 02 sensors. One of the sides is a real pain to get too, I think it was the passenger side. Much less frustrating using the tool than the other tools/ways I tried.
FWIW, I changed my upstream sensors out at 160,000 and the live data stream indicated no difference. MPG didn't change at all.