I just personally prefer Google's way of serving ads - much better than banners (or even worse Flash banners, or ads with video clips). Sometimes links are even clicked on as they are related to the content of the page you are on. Google keeps things simple, rather than try and impress people (although Gmail is actually quite impressive, very little unneccesary content is served).

The privacy violation could occur with Hotmail as well - I am sure cookie tracking is used to some extent. They would only get information from you if you actually clicked the ads.

As I said before, if you wish to keep your email private don't use web based email like Google / Hotmail / Yahoo etc. For that you should be using your companies email anyway (or even host you own email server).