@fcpprs @BGR @ajg As spotted by @Kommissarmartin here, this happens when an app which uses the Play Services (such as Find My Device) is enabled as a Device admin.
To fix this, go to Settings > Security > Device admin apps and disable the services there. After you deinstall the Google Play Services updates, you can go back and enable the Device admin apps again.