I've gone the Google-free route a little while ago, and it's really been not nearly as bad as even I thought myself.
The only thing that I'm still sort of missing, is the automatic calendar and contact backup.
You could do that with something like OwnCloud/NextCloud or a CalDAV-service, but yeah, it is a non-trivial effort.
Otherwise, in case you do try it, here's some things that I found useful:
If the apps on F-Droid aren't enough for your taste, you can also use Aptoide [0] to access a big portion of the apps that are available on the Play Store.
The Amazon Store is also an option, although their store is also not really the greatest when it comes to not invading your privacy.
And if you cannot live without some of the apps on the Play Store, or if you've paid for some apps there and would prefer to not lose access to them, I can recommend Raccoon [1] for accessing them.
There's also some online-services, like for example Evozi [2], which can download unpaid apps from the Play Store for you, but well, for one, usually only unpaid apps, and secondly, I have yet to find one of those services which is not hopelessly overloaded.
I think, if you look more into app-piracy tools, you might also find a web-service which let's you download paid apps, but I've personally just stuck to Raccoon, so I can't make any recommemdations there.
Finally, if one of your apps really does need Google Play Services, there's a project aiming to reimplement the functionality without the privacy problems, called microG [3].
I haven't personally tried it yet, but I think, it's somewhat hit-and-miss, so while it's probably worth trying, you shouldn't expect too much from it...
[0]: http://www.aptoide.com/
[1]: http://www.onyxbits.de/raccoon
[2]: https://apps.evozi.com/apk-downloader/
[3]: https://microg.org/