The tower change is not a MUST unless the fuel:air ratio needs adjustment after the new O2 sensor is changed. I usually count on having to adjust it, which is why mine was drilled out and plugged up with a bolt for future access.
BTW, listen to MBDOC, since some of your problems are cold running problems and probably not O2 sensor related, check with another mechanic. It may be worth your while.
If you include the tower change, the time is probably right. I would not consider that a DIY'er. Not because of the difficulty but because of the risk of dropping something into the intake manifold.