Does it recover with WOT(wide open throttle)?
The computer operating the engine(the PCM) has two operating states:
Open Loop, when engine is cold or at WOT, in this state the PCM ignores most sensors and runs a preset fuel/air mixture based on Throttle position(TPS) sensor.
Closed Loop, when engine is warmed up, the PCM uses sensors to set fuel/air mixture, and the TPS.
What tells the PCM that the engine is warm or cold is the Engine coolant temp(ECT) sensor, it is a two wire sensor near the t-stat housing, the 1 wire sensor near it is for the dash board temp gauge.
When you turn off the key on a warm engine and then turn it back on, the PCM has a timer that waits for a minute or so for the O2 sensors to warm back up, they need to be above 600deg to work properly.
A bad O2 sensor can cause running issues but not sure it would be as described.
The key off then on is interesting through.
Could be fuel pressure issue, when you cycle the key off then on again the PCM runs the fuel pump for 1 or 2 seconds to prime the system, which if pressure was low would get it back up until it dropped again.
That could be fuel pump failing or plugged fuel filter, even the fuel pressure regulator on the rail.
Fuel filter is only $10 and not to hard to change.
If possible check the pressure at the rail, should be 30-40psi, check it with engine off and with engine on.