Google could offer a $20/month no-ads no-tracking email service. How many privacy conscious people are willing to pay that? Its not Google deciding to do this, its just ourselves.
According to their homepage, 5 million businesses have chosen that.
http://www.google.com/enterprise/apps/business/
No tracking is trickier, who would believe Google (or any business) if they claimed they didn't track their customers? The lack of ads you can verify for yourself.
Although I don't trust Google on privacy, this deal would benefit me - I get to take away the worst aspects of Gmail while keeping the better aspects.
However, I wonder if offering this service as an option would generally drive people away from free-Gmail: it would serve as an direct admission and reminder that ads and tracking are not really desirable.