How to remove Google Play services? I want to increase my ability to remain anonymous, or at least make it harder to track me. I want to remove Google Play completely from a Samsung Galaxy S4 running Android 5.0.1.

Android works fine without Google Play. I've been running Cyanogenmod without it for a few years. Besides a few dysfunctional/crappy apps that crash because there's no Advertising ID, everything works fine.

I also don't play games or use their app store. When I find something I want, I build it from sources and install it over adb. Or I write it myself since I have a development background.

I tried to remove and disable all the Google Play stuff through Settings, but nothing has worked to date. Usually the option to remove or disable is not available (its greyed out). Or if I disable it, then the phone ignores my wishes and immediately re-enables it.

How do I remove Google Play services?
I think your best solution would be to root the phone and then you can uninstall all the system apps you don't want.

To root the Samsung you could install TWRP custom recovery; boot into it (Home + Vol Up + Power) and choose to root the phone.

You could go a step further if you wish by installing cyanogenmod which does not come with Google apps by default.