I was answering under the assumption/the context of of "Amazon wants to release an Android-based OS that doesn't contact any of Googles services".
So, when I said "easy enough to remove" that was relative to releasing any commercial OS based on AOSP, as in: this will be one of the smallest tasks involved in this whole venture.
They will need an (at least semi-automated) way to keep up with changes from upstream and still apply their own code-changes on top of that anyway and once that is set up, a small set of 10-ish 3-line patches is not a lot of effort. For an individual getting started and trying to keep that all up to do date individually it's a bit more of an effort, granted.
The list you linked is very interesting, but I suspect that much of that isn't in AOSP, my suspicion is that at most the things up to and excluding the Updater even exist in AOSP.