How do you do this for services where functionality is reliant on tracking etc? E.g. some of Google's services.

You can only degrade when the users denial exactly relates to the function of the service.

I have history turned off in google maps. I can’t name the points I make, it tells me I need to turn history and tracking back on. I hope that becomes an unjustifiable degrade.

I may have understood wrong, but it seems to me that for your maps degrade, the tracking may relate very much to the function of the service. How is the server supposed to remember the name you gave to each point without tracking you? Remember, there are many round-trips to the server when you're scrolling and resizing a map. They could always move point-naming override client side, but that's a pretty big change.

You don't do these services without obtaining the user consent first. Simple as that.