This sounds a similar (but more severe) problem to what I experienced consistently with my 2000 GT-S, but it was something I attributed to my MAF sensor being dirty.
It ran poorly for over a year until I took it into a random shop on the side of the road (took it to a recommended shop twice previously and they were clueless) and they had it solved in 2 hours. Basically all they had to do was clean the MAF sensor and my baby was running like hell on wheels again.
I've read articles that say you can clean a MAF sensor by unloading a can of CRC contact cleaner onto the sensor (no touching! no blow drying!). Maybe give that a try?
P.S.: My apologies if O2 and MAF are the same sensor, but
afaik they are separate parts, and the MAF is far more accessible.