My first thought was BonziBuddy: a free "assistant" program that was monetized by capturing and selling your personal data and displaying ads directly.
The Google toolbar specifically had a privacy settings popup with a big fat red "PLEASE ACTUALLY READ THIS" notice, explaining what it does, and letting you choose between a mode that only worked locally (unless you were making a search or explicitly triggering some other online feature of course) vs. one that sent some data to Google with each visit (with PageRank display being tied to sending the data).
Users weren't pushed to choose one or the other. Both buttons had the same size and color. It was VERY clear that the developers wanted users to make a meaningful, free choice vs. "just click approve".
The benefit for Google was that installing the toolbar made it easier for you to do Google searches, driving usage up.
