Google should invent a distributed, encrypted email protocol and make that network an option in GMail for storage and message sending. That would be a great PR move - if there is no central server, and no central message pipe, it's a little hard for anyone to think Google wants to be complicit in spying.
For users who are willing to give up the web interface, there are many open-source email clients that provide strong encryption (e.g. Thunderbird + GPG).