I just finished most of this transition for my own purposes, with the main difference that I decided to self-host most of the services I was previously using Google for. Some highlights:

* Android: if you really want to divest yourself from Google, Android is going to be a showstopper for any but the most committed people. I'm running LineageOS (nee CyanogenMod) without gapps, using microG as a collection of play services API replacements. While that keeps me from adding a google account to the phone (which is the main thing I'm trying to avoid), I still end up needing something like Yalp Store (available from F-Droid) to download and update Play Store apps, because there are a few I actually can't get by without a huge level of inconvenience. I did all this because I enjoyed the challenge of it; for normal people who aren't intrinsically motivated by this stuff, I suggest buying an iPhone and saving yourself the headache. Seriously.

* Email was the easiest thing to move, and the hardest to get right. I remember when I originally moved my email to Gmail, and noted a marked increase in spam; the same thing happened when I moved off of Gmail last month. A combination of postfix, dovecot, spamassassin, and a lot of tweaking has me mostly back to the point where I was when I was with Google. I've been using Rainloop for a use-anywhere web UI, although I've used Roundcube in the past and was pretty happy with it. On mobile, I'm actually using k9mail, despite how dated it is, because it actually gets IMAP right; both the stock "Email" app and Gmail had sporadic issues with IMAP that I got tired of dealing with.

* Meanwhile, calendaring was the messiest part of the move, mostly because CalDAV is a bit of a mess, and both client and server implementations leave a lot to be desired. I ended up using sabre/dav on the backend because I could tweak and extend it quite a but to do what I need, and because it had baked-in support for CalDAV scheduling, which is something I can't really live without. I'm using DAVdroid on Android for both calendar and contact sync, which is great except for scheduling, which I can't really use. (A combination of what looks to be some misbehavior in davdroid, and android limitations in the calendar API.)

* More calendaring: are you used to having your calendar invites just magically show up in your calendar? Yeah, that's probably not going to work anymore. I'm been writing an itip milter that scans for text/calendar mime parts in incoming email and shoves them in an appropriate caldav store, but it's going to be pretty hacky even if I finish it. ;) If you're looking for better integration here, look at something like Zimbra; it's a huge pain in the ass to run, and it's resource-heavy, but when it's running well it's amazingly polished from the end user's perspective. Or give FastMail some money, because they've been doing this for a long time, and do it really well.

* Docs, photos, file syncing in general: There's a bunch of options here. I almost ended running an instance of NextCloud (nee OwnCloud) for this, because it would cover a few different use cases (document storage, photos, calendaring, contacts, etc), but settled on Syncthing as a general file synchronization tool. I'm hosting a cloud instance that my laptop, mobile devices, etc. can all talk to, as well as an instance on a machine at home, giving me pretty good coverage for on-demand backups. I try to avoid working in heavyweight document formats for personal stuff (markdown and a text editor works for my use case most of the time); for things I have to share or where I need more powerful tools, LibreOffice. I don't have a good photo management solution right now beyond "directory full of photos synced from my phone and camera".

* Books: I had bought a bunch of books on the Play Store. This was a painful lesson in how bad the state of DRM in ebooks is, especially if you don't have a Windows machine lying around. I ended up having to install Adobe Digital Editions under Wine, then used a Calibre plugin to automatically convert DRM'd ebooks via ADE when I have it import them. I share the Calibre collection to my tablet via syncthing, so changes, read positions, etc. sync nicely. (I don't mean to pick on Google on this one; the DRM issue seems to be a mess with every bookseller right now.)

* Music: Exported my music using Music Manager, sync with Syncthing, and access streaming music with Spotify. Done, easy.

* Maps: I use Google Maps, logged out (it's one of the few Google apps that continues to function properly even without a Google account on the device). OsmAnd~ is a great idea, and I use it as a fallback when I'm outside of cell coverage, but I find it almost impossible to use in a day-to-day context (if you have it open gmaps links/intents, it almost never figures out the address I'm looking for, and I've had terrible luck relying on it for navigation). Note that without logging in, you cannot save Google Maps data offline, because apparently gmaps engineers are a little bit spiteful.

* Search: I've defaulted to DuckDuckGo for years. Yes, sometimes I hit "!g" to search Google, but I don't default to them, and haven't for a long time. Also, shock of shocks, bing is getting pretty good.

* Android Pay: I opted out. I have credit and debit cards, and I have cash. Some people might find this to be a deal breaker, I find it hasn't changed my life in any significant way.

* Browsing: Firefox. Not really a change for me.

There's a bunch of smaller one-off services that I've used over time, but those are the big ones from a personal perspective. For some folks, a large chunk of these can be handled by running an instance of NextCloud, and you'll get a polished, fairly integrated experience for the parts they can cover.

At some point, I should probably write this up with more details about the tradeoffs I made with each piece.