I'm struggling to glean any meaning out of multiple explanations of HATEOAS beyond "response bodies with hyperlinks in them". Whatever it is, it's too unstructured for computers to automatically use, and unnecessary for humans, who are quite capable of using, well, any website designed for a human

HATEOAS is the name Fielding came up with when philosophizing about the architectural style of the Web circa 2000 and how it differed from other architectural styles. That's all it is. That it's "too unstructured for computers to automatically use" is not a failure case, because there was no objective other than to describe how the Web worked. He was developing a taxonomy—of the world as it is—not trying to invent something new and admonishing people that "Hey, this is how we really ought to be doing things", unlike many of the articles that you've probably read about the promises of this whole "REST" thing, right?

If you expect it to be anything else at this point, then you are sure to end up disappointed, because you are setting yourself up for failure. Kinda sucks that an entire industry misled you into thinking otherwise, but that is its wont...

Think of a "traditional" web application (Django, RoR, etc).

Say, one day you decide to completely rewrite it -- add new pages, remove some existing pages, change the site structure (as in which pages the user can navigate to from a given page). While the app has changed beyond recognition, the user doesn't need to download a new version of browser, they can still point their existing browser to the app's home page and it will just work. This is an app based on the REST architectural style.

Now, if instead of such a web application we have one based on a binary media type instead of HTML and a custom client instead of the browser, but otherwise everything described above still apply, this is a RESTful app too.

If a decoupling like this is a priority for an app, REST is a good choice for it.

There's a trade-off, of course. While the client is decoupled from the server along one axis, they are fundamentally coupled along another. Imagine a RESTful banking app, and let's say we would like to add a list of recent transactions to the home screen of a mobile client, but the server resource representing the home screen doesn't encode this list in any way. Well, there's is no way to just add it on the client in this case, at least without breaking the principles of REST hence defying the whole purpose of choosing this architectural style in the first place.

We have to change the backend code any time we want to change what's available on one of client screen's and where the user can navigate from that screen. This can be a deal-breaker limitation for a lot of apps. They're better off designed around another architectural style -- an API having pretty URIs for endpoints, JSON-serialized request/response bodies, utilizing HTTP method for CRUD operations is one such alternative.