Lineage and GrapheneOS don't rely on Google Play services. It's your apps that depend on this proprietary bullshit. That's exactly why we need to grow the Android FOSS app ecosystem. We already have FOSS app marketplaces like F-Droid and Accrescent, and Obtainium allows us to download APKs from GitHub releases, as well as many other sources. There are many great FOSS apps that work just as well or even better than their proprietary counterparts. Some of my personal favorites are Breezy Weather, AntennaPod, Thunder for Lemmy, Aegis for 2FA, Standard Notes, LibreTube for YouTube, Xtra for Twitch and Translate You. There are alternatives for basically any Google service. We have UnifiedPush for notifications, OpenStreetMaps for maps and navigation, various serach engines like DuckDuckGo, Qwant, Mojeek and others (Android now even asks the user what search engine to use, instead of selecting Google as the default). There's an improved fork of Signal called Molly, which has a FOSS variant that doesn't use any proprietary Google libraries, it supports notifications through WebSockets instead of relying on Google's FCM and they even have an option for UnifiedPush.