I'm not strictly advocating HATEOS. Hypermedia and HATEOS are related but not the same concept. I am very strongly advocating hypermedia, as I believe it it greatly reduces the complexity of interacting with an API.
Never having to build a URL by hand is great! Being able to just grab a field from a resource, and go do a GET on its value is very easy to code, even if that process involves finding a link with a certain relation. You speak of complexity, and I'm speaking of convenience.
With that convenience also comes the ability to automatically crawl the data with good solid knowledge of how each resource relates to others, enabling the ability to create massive graphs of information. Like wikipedia has for humans to read, but structured and standard for computers to parse.
> His theoretical (well, implementations certainly exist) universal REST client only works when every API you want to consume standardizes to presenting the information in the same format.
That sounds like a great day to me.