At the end of the day, people don't read privacy policies.[1] They depend on intuition: if I watch a lot of cat videos on Youtube, I might get ads for cat products. When your data analysis goes outside the boundaries of what users would intuitively expect based on their knowing,[2] and voluntary interactions with your service, then I think you're on shaky ground.
And no, it's not a Google-specific problem. Google is just the face of this new industry based on privacy-monetization, and the criticism it gets is to be expected based on its leadership position.
[1] And I think it's wrong-headed to infer consent from inaction.
[2] When you're talking about, e.g., Android, many users don't even realize they're interacting with Google services.