It may be hard to recall now, but their big thing was actually less intrusive and less scammy ads than the state of the art at the time.
It's also worth mentioning that lots of businesses that you pay money to, track you in similar ways. The origin of it was probably supermarket loyalty cards in the pre-internet era.
The association with no-cost products is not really appropriate, and mostly seems to be progaganda from people with other business models. It was the web scale and pure digital products that let the cost drop to near zero, which synergises with ad-supported offerings, (just as "free" ad-supported TV and radio were a thing for decades). However, it also allows other business models, such as non-profits like Wikipedia, netflix subscriptions, or subsidized by necessary hardware purchases.
Similarly, just because you pay money for various Google services, doesn't really gave them any motivation to not track you.
