RE: starting bad
Zack,
Have you checked fuel pressure? Did you have a fault code or other indication that the O2 sensors were the source of the problem?
One possibility (verfiable with a fuel pressure gauge) is that the the pump (or regulator) lets fuel pressure bleed off when the pump is not running/engine turned off.
An easy test (although not foolproof) would be to 'cycle' the key to the run position and off a few times before actually cranking the engine. If the engine starts properly after three or four key cycles, the indication would be that fuel pressure is being lost when the engine (and therefore the fuel pump) is shut off.
Okay, all this may be jumping the gun a bit; do you have fault codes? Low fuel pressure?
Good luck!