Additionally, they are all rolling out DPI ad-serving platforms that sniff your traffic (and I'm sure also sell it to any .gov with a dime) -- AT&T being the current worst offender by charging a $30 a month penalty if you try to opt out of it. (See www.dslreports.com/shownews/ATT-Offers-70-1-Gbps-in-Austin-With-a-Big-Catch-126969)
They're a corporation. They can charge you to not spy on you because you don't HAVE to use them. It would only be illegal if they spied on you without you signing their contract.
Edit: It's the same way that when you agree to the TOS of a service like, xbox live or something, if they had a line about how you can't talk badly about Xbox or they delete your account, it's not breaking the first amendment, because they aren't the government, and you consented to that agreement.
Just a sidenote; TOS are not concrete law-binding forces. You can't put "unreasonable" things in a ToS. If MS dropped a gamer's subscription because she complained about XboxLive on her Twitter, she could take action against MS and have a chance of winning if a Judge says "You can't tell people not to complain". Also, I'd be very annoyed if I ever heard of a company dropping customers who complain about them. I think that's unreasonable. Every successful company I've ever heard of has complaints about them.
NOTE: A "normal" complaint is different from outright excessive/exaggerated slander.
The law obviously isn't as simple as that. If I agree with an electrician that I will pay him or her to install a switch that we are both aware is unsafe and against building codes, that is still illegal.
That isn't really relevant here, though. The contract in this case is essentially "We'll give you a good deal on high-speed Internet in exchange for letting us serve you context-sensitive ads. You can of course opt out of the ads, but then we'll charge you more." No element of this contract involves breaking the law, and no element of the contract places unusually burdensome requirements on the customer — you just decide whether you'll accept $30 to let AT&T show you some ads.
(The fact that AT&T's ad-supported plan is not a better deal than Google's fiber plan is not really material. It isn't generally illegal to have an inferior product or to charge more than your competitors for the same goods.)
You're not paying $30 extra to opt-out. They're giving you a $30 discount for you to hand over your data.
It's the same way gas stations get away with "charging extra" for credit. Most credit card vendor agreements do not allow the merchant to pass along the 3% or whatever fee to the customer. So what the gas stations do instead is give you a "cash discount".
This is no longer true re: credit cards. As part of the consumer protection package that passed a few years back, charging fees became permissible by merchants.
Thanks to Snowden's revelations, Internet traffic will be fully encrypted sooner rather than later. They can't serve you ads if they can't examine your packets.