O2 sensors either work or they don't. If they don't, it'll trip the CEL. If they do work & you swap them out, no problem ... but it won't help the gas mileage. You're better off attacking the other stuff people mentioned before you replace the O2.

Even though you just had the tranny serviced, check the level anyway. IIRC, the process for checking your tranny fluid level is somewhat complicated after a change. I think there is a how2 in the ... wait for it ... the how2 section. Also, the next time it is slow to engage, look at your indicators in the dash cluster. If the lights don't match what gear you are in, the shift sensor may be bad/dirty.