But that doesn't mean that they give or sell your data to other companies. In fact, that would be incredibly stupid, each bit of data you can sell only once, while as space, you can sell every day.

Is there really such a major difference between you giving your data to your email provider who then sells it to other companies or you giving data to your email provider who then uses it very much the same way these other companies would do?

One major difference is that data is sold tends to get a life on its own. Company A sells to B, B to C, etc. Before you know it, your e-mail address/phone number is in the hands of many companies.

Google is different in this regard. Since they don't sell raw data, it's easier to opt-out (remove data via the Dashboard[1], delete your account, etc.).

[1] http://en.wikipedia.org/wiki/Google_Dashboard

Fair enough, that is indeed a – possibly major – difference, although Google department A sharing data with department B, which gives stuff to department C could be argued to be similar, as the size of these departments easily match those of other companies.

Correct … but do not forget that there is Google Apps for Business too where you are not shown any ads.