I personally don't find Gmail's changed privacy policy a big deal, but the drop off in quality and speed between GMail and other free webmail alternatives is pretty steep. Hotmail has improved to be the 2nd best, but I don't see how allowing MS to data mine your email is worse than allowing Google to do so.
There's a reason why these services are free. Then again, I can't think of a single paid email service that offers anything as compelling as GMail. And buying your own domain, server space, configuring a webmail interface and turning on access is a PITA.