Sounds like it's acting up when it goes into open loop, it's warmed up. Vehicle doesn't really acknowledge most of the sensors until it goes to open loop; it uses predefined parameters to run(not the most efficiently, but able to run). Since you have already put in a good quality O2 sensor i'd presume it's not that. MAP sensor could be flaky but you will usually get a code for that too, but a vacuum leak will influence MAP values, so check ALL your vacuum lines there aren't many. I suspect a ground, maybe the straps on the back of the passenger head. I live in Florida too, they go green after so long.
EGR valve was a good thing to change. My old one had a perforation and wouldn't hold vacuum and the truck had a stumble off of idle that was noticeable when taking off from stop. Never threw a code I changed it on GP.
It would be worth checking your oxygen sensor ground. Based on your year you should have the 1 wire sensor which will get its ground from the exhaust system. This is less than ideal on an old vehicle. If the ground is not good this WILL cause erratic readings from the O2 sensor and WILL cause problems when in open loop. I have had good results in past vehicles from switching out a 1-wire O2 sensor to a 3 or 4 wire sensor. The extra wires are for the heater and a ground. You can wire it up on a relay that kicks on the O2 sensor heater only when the ignition is on. The computer gets quicker and better readings from the O2 sensor and the sensor stays cleaner over time, won't get all crudded up from running cold. Also, if you have made some extreme exhaust modifications that would alter the location of the O2 sensor it may not be warming up.
The other vehicle I had ended up needed new fuel injectors before it ran like it was supposed to. The O2 sensor just helped things.