I've tried GrapheneOS and it works great.

You can setup an android phone with everything you need, and nothing from Google.

Here are some really useful apps:

• F-Droid. App store with direct APK downloads.
• DAVx5. Allows you to use your own CalDAV/CardDAV/WebDAV. That means you can sync your own calendar, and contacts. No need for external services.
• Simple Contacts Pro. Beautiful and simple Contacts app. Works with DAVx5.
• Simple Calendar Pro. Beautiful and simple Calendar app. Works with DAVx5.
• Fair Email. This is an excellent email app that works with your own email server or any other email provider. No ads, just great stuff.
• AntennaPod. Open Source Podcast player. Works great.
• Organic Maps. Maps with routing directions. Works offline as well.
• Bitcoin Lightning wallets. Some of the best ones out there, with direct APK install.

And there are more apps out there, but those should cover the basics, without the need of Google.

If you do need to use certain apps that require Google Play Services, like Uber, WhatsApp, etc, they all work as usual, but you need to install the sandboxed Google Play Store from the menu. It will install a limited version of it, allowing apps to connect to Google. It's recommended to only install this on another profile and keep your main profile free of Google, for better privacy.

Graphene is so epic