m4ri0g Tracking, whether in the presence or absence of Google Play is an incredibly complex issue. My question would be, do you use apps where you provide personally identifiable information such as contacts, social media, banking/payment apps or similar? If you do, chances are you have leaked some of that information. Despite recent Android changes, apps still have plenty of opportunity to collect various software and hardware IDs and something what I would call zero day IDs, which by themselves can be enough to uniquely identify you. That, coupled with any collected personal info can lead to your true identity.
I am painfully aware tracking isn't going to disappear any time soon, if ever, by removing the perpetual collection Google Play provides along with more than likely IPC. Unfortunately, I am also reliant on certain proprietary apps with network access where data collection and remote analytics is expected.
Now, some may say that many people do not worry about this, as long as they operate in a safe environment with quick updates and extra features GrapheneOS provides. But then again, at least as many do.