Here’s my current take …
I try to walk a line between de-Google-ing the phone while keeping the basic Google Mobile Services (GMS, for OTA updates of the OS and some Play Store Apps I still have as APKs for installing) and the Play Store itself (for updates of remaining Google components) from breaking, even if I try not to use my Google account for now.
I’m not a big fan of installing downloaded APKs from some website without an automatic update possibility which stores like e.g. F-Droid provide, but it seems this will be necessary for now in some cases if I don’t want to compromise too much.
Replacement Apps
Calculator: Arity from F-Droid
(I tried Calculator from F-Droid, too, but it’s really basic. When I seldomly need a calculator, I want to have some advanced stuff. I didn’t try Simple Calculator from F-Droid, because it looked pretty basic on the screenshots, too.)
Calendar: Simple Calendar Pro from F-Droid
(I don’t work much with the calendar, I just sync my few calendar events from Thunderbird to it … I tried Etar from F-Droid, too, and it would work for me as well.)
Camera: Google Camera with HDR+, Nightsight etc. (Xiaomi Poco F1 port) from XDA
(I kept the original Camera App, too, for the moment … can’t decide just now whether to omit it or not.
A well-known and widely used non-Google camera App would be Open Camera from F-Droid.)
Clock: Simple Clock from F-Droid
Contacts: Contacts 1.7.31 by LineageOS from APKMirror
(I tried Simple Contacts from F-Droid, but it can’t put shortcuts of contacts to the home screen, and I absolutely want to have that. Furthermore, one out of two times I tried it, Simple Contacts couldn’t see my contacts when Dialer and LineageOS Contacts could … weird.)
Dialer: Lineage OS Phone 19.0 by LineageOS (Variant: September 21, 2018) from APKMirror
(As Emerald Dialer from F-Droid seemingly doesn’t cut it yet.)
Files: Ghost Commander or Amaze from F-Droid
(There’s still a use case for Files, though.)
Gboard: Simple Keyboard from F-Droid
(Attention! This will not work with a password as unlocking method, use a PIN instead.)
Gmail: Email 9 by LineageOS from APKMirror
(I tried SimpleEmail and FairEmail from F-Droid, both pretty similar K9 forks, but I didn’t like them.)
Google Chrome: Fennec F-Droid from … well … F-Droid
Google Maps: OsmAnd+ from F-Droid
(In case of need Google Maps has a usable website.)
Google Play Store: Aurora Store from F-Droid
(I deactivated the Play Store since Aurora got anonymous login to the Play Store back.)
Launcher: Lawnchair from F-Droid
(I tried Trebuchet from XDA, too, which would work for me, too, but with F-Droid there’s at least a way for automatic updates, even if there are none in sight in this case for now.)
Messages: QKSMS from F-Droid
Music: VLC from F-Droid
Photos: Simple Gallery Pro from F-Droid
Videos: VLC from F-Droid
YouTube: Has a usable website.
YouTube Music : Don’t need it. (Was installed with OS Build number 8901.2.A.0101.20191115)
Mentions for convenience
Simply Solid from F-Droid
(Apparently Android by default has no way of setting a plain colour as background for home and lock screen, it wants to have a picture. If you just want to have a plain colour, Simply Solid saves you from having to make a picture of a plain colour yourself.)
Your local weather from F-Droid
(As far as I’ve seen, the original weather Widget was part of the stock launcher. If you want to have some Widget choices for your weather, here’s an F-Droid App that gives you some. This works especially well if you have your own OpenWeatherMap API key.
There are other weather Apps on F-Droid, too.)
Still there
com.android.documentsui … Files (see above)
com.android.fpcamera3 … Camera (not yet uninstalled)
com.android.vending … Play Store (on purpose, see top)
com.google.android.apps.work.oobconfig … What does this do? Android Work Profiles perhaps?
com.google.android.configupdater … auto updates certificates, firewall configuration, time zone info
com.google.android.gms … Google Mobile Services, important for Apps relying on them and for receiving SMS Edit by @Stefan: Not true (QKSMS and Silence work), see here.
com.google.android.gsf … Google Services Framework, important for Apps relying on it and for receiving SMS Edit by @Stefan: Not true (QKSMS and Silence work), see here.
com.google.android.ims … Carrier Services
com.google.android.marvin.talkback … Android Accessibility Suite
com.google.android.packageinstaller … sounds harmless
com.google.android.printservice.recommendation … What does this do?
com.google.android.tag … Google Tag Manager, may be used by Apps
com.google.android.tts … Text-To-Speech engine, missing TTS may be inconvenient with Apps used for navigation, and there’s no real FOSS alternative right now. Let’s believe TTS conversion is being done locally.
com.google.android.webview … Android System WebView, handle with care.
Uninstalled via adb shell pm uninstall --user 0 packagename
(and watch out for App updates which might still need to get uninstalled)
com.android.chrome … Google Chrome
com.android.launcher3 … Stock launcher
com.android.providers.partnerbookmarks … sounds useless
com.google.android.apps.docs … Google Drive
com.google.android.apps.maps … Google Maps
com.google.android.apps.messaging … Messages
com.google.android.apps.photos … Photos
com.google.android.apps.restore … sounds useless when I backup and sync locally
com.google.android.apps.tachyon … Google Duo
com.google.android.apps.wellbeing … Digital Wellbeing
com.google.android.apps.youtube.music … YouTube Music
com.google.android.backuptransport … Implementation for the Android Backup Service, providing key/value cloud storage for apps.
com.google.android.calculator … Calculator
com.google.android.calendar … Calendar
com.google.android.contacts … Contacts
com.google.android.deskclock … Clock
com.google.android.dialer … Dialer
com.google.android.ext.services … Android Services Library, sorts notifications by “importance” based on things like freshness, app type (IM apps come first), and by contact.
com.google.android.ext.shared … Android Shared Library, what does this do?
com.google.android.feedback … I don’t give any, at least not willingly 
.
com.google.android.gm … Gmail
com.google.android.gms.policy_sidecar_aps… What does this do?
com.google.android.gmsintegration … Google Sample Home Screen
com.google.android.googlequicksearchbox … “Google”, literally
com.google.android.inputmethod.latin … Gboard
com.google.android.music … Music
com.google.android.onetimeinitializer … This is the setup wizard when you first run your phone.
com.google.android.partnersetup … What does this do?
com.google.android.setupwizard … setup wizard from Google
com.google.android.syncadapters.contacts … Google Contacts Sync
com.google.android.videos … Videos
com.google.android.youtube … Youtube
Some complementary settings
I’ll just list some settings here for reference without much testing yet. Maybe I’ll retract some later when I realize they break stuff.
Some default values of settings might be clearly useful under certain circumstances, so please make up your own mind at every step you take.
First time setup
Make some sensible choices about Google’s immediate involvement when you first start the phone (or after a factory reset) concerning location, backup, sending usage data etc. … and don’t add a Google account.
Skip logging in to a Wi-Fi network and immediately disable Mobile data in the quick settings once you reach the home screen, until you first have initially checked through the Settings tree whether you can prevent some Google “damage” already.
Settings
-
Accounts (I know it’s not on top in reality, but it’s important.):
Don’t add a Google account here (or by other means like the first time setup assistant or else) if you don’t really have to.
If you really have to, first turn off “Automatically sync data” here, then add the account and perhaps try to minimize syncing in its settings, then turn on “Automatically sync data” again, then check the settings of the Google account again to be sure.
-
Network & Internet
- Wi-Fi
- Wi-Fi preferences
- Advanced
- Network rating provider: None (instead of Google)
-
Apps & notifications
- Default apps: (Make sure non-Google replacement Apps are set here, if any.)
- App permissions
- Body sensors
- Google Play services: Off
- Calendar
- Google Play services: Off
- Call logs
- Google Play services: Off
- Camera
- Google Play services: Off
- Contacts
- Google Play services: Off
- Microphone
- Google Play services: Off
- Additional permissions: (Nothing interesting set here for me, but you might want to check.)
-
Security & location
- Google Play Protect
- (cog wheel top right)
- Scan device for security threats: Off
- Find My Device: Off
- Location
- Google Location Accuracy
- Improve Location Accuracy: (Turn this off to make it harder for Google to know which Wi-Fi and mobile networks you hang around. Location would purely rely on GPS then and might be more inaccurate/ unavailable e.g. indoors.)
- Google Location Sharing: (I don’t know what’s in here without a Google account.)
- Advanced
- Scanning
- Wi-Fi scanning / Bluetooth scanning: (I don’t know whether they are Google-related, but judging by their description it seemed sensible to me to turn them off.)
- Advanced
-
System
- Languages & input
- Virtual keyboard: Simple Keyboard (see above, or choose your choice of non-Google keyboard here, tap on the App here to check its settings.)
- Advanced
- Spell checker: (Make sure Google isn’t involved here, I have this off anyway. Yeah, “sometimes it shows, haha” … mostly when I’m not quick enough proof-reading/ correcting
.)
- Auto-fill service: None (instead of Google)
- Languages & input
- Backup
- Back up to Google Drive: Off
-
Google (I know it’s not at the end in reality, but some settings here are just links to settings in other places in the Settings tree, so I can leave them out here.)
- Ads
- Opt out of Ads Personalisation: On
- Data & messaging
- App preview messages: Off
- Device connections
Issues so far
- Current DB Navigator (tested with 19.10.p03.02) crashed at start.
A re-install after uninstalling it failed.
Workaround: Earlier DB Navigator (tested with 19.04.p05.01 and 19.08.p03.00) worked.
The issue was a split APK,
logcat entry was “Package de.hafas.android.db blocked since it is missing required splits.”
Solution: SAI (Split APKs Installer) from F-Droid can handle split APKs.
Major catch: The App in question has to work first. Then you can export the split APK of it with SAI, and then you can install the resulting split APK with SAI again if needed
(confirmed with 19.10.p03.02 by deactivating all syncing, adding my Google account, installing current DB Navigator from the Play Store, exporting the split APK with SAI, uninstalling the App, removing my Google account - losing all contacts because Google simply assigned them to this account, be safe with a backup! - , enable syncing again, installing the split APK with SAI).
Side effect: Dealing with this confirmed the Play Store still works if I want it to, and DB Navigator didn’t break because of all the uninstalling of Android components.
-
Dialing *#*#4636#*#* doesn’t bring up the “Testing” menu.
Seems to have resolved itself.
- After the update to OS Build number 8901.2.A.0101.20191115 (and after every reboot since) Android complained about Carrier Services not being able to work correctly, if I wouldn’t give Google Play Services permissions to Body sensors, Calendar, Camera, Contacts, Microphone (it’s all in one place, see above) … I didn’t give the permissions, let’s just see if something breaks. Until now the phone was working fine.
