I use both. Melodyne 3 and Autotune 4. They ar both good. Melodyne is very easy to use though. If I had to choose just one, I'd choose Melodyne.
what does auto-tune offer that melodyne doesnt? or vica versa?
You will have to demo them for yourself.
The biggest difference to me is the GUI. Autotune is not as friendly.
Melodyne has some options that will allow you to use it as a DAW and not just a plug like Autotune.
Watch the videos
I just bought Melodyne (the VST). All I can say is wow, A first listen it sounds much better than I thought it would, and it seems pretty easy to use.
Melodyne 10 times out of 10. Autotune is not bad, but Melodyne is so much more feature rich and easy to use.
Pro Tools V.7HD Certified Operator
G4 dual 1 GHz