Current status:

I did:
- Tried looking for a fuse, couldn't find one.
- Can't figure out which relay is the one that controls the O2 sensor.
- Tried pulling the fuse to the computer for a couple of hours, didn't fix it.

Took it back to the repair shop. They did:
- Traced and measured voltage and resistance on the wiring to the O2 sensor, all good.
- Checked voltage at the relay (they apparently know where it is). Good.
- Measured resistance across the the O2 sensor itself. Not in spec, they said it's only 3 ohms when it should be much higher than that.
- Tried another O2 sensor, it also did not fix it, and also didn't have the resistance value they expected.

Next step:
Monday they will try to order an OEM Honda O2 sensor. If that doesn't work, then they want to look at the computer as a possible culprit, but I'm not down with that.