> "What you did not do is build an REST API"The API here is HTML + HTTP. That's it. A website is, as far as the API is concerned, just the content.
> "I want to get the data and compute some statistics on it. For that I need to know the structure of the data in advance, need to know which URLs to retrieve, which operations to perform, which data structures to expect"
Not needing to know the structure to automate usage of the content is not something that was exactly "promised" by REST. REST/HATEOAS is only about having standardized formats to display the hypermedia, make it discoverable within constraints (a browser for HTTP/HTML, a database program for OData, etc).
Even with websites, I might need previous knowledge to know where to navigate to, which URLs to access. When I come to Hacker News, I always click on "threads" at the top to see if anyone replied me. This is often discovered thanks to hypermedia (in this case a link). But in my case someone had to point it out to me (this is analogous to documentation).
> "So what am I still not getting?"
My assumption, but since you asked: I think you're expecting the original REST paper and hypermedia to be something that it isn't, and to apply to things it isn't supposed to. You're trying to apply it to arbitrary APIs that are supposed to be consumed exclusively by custom software. This doesn't really match its model or intent.
HTTP/HTML content is consumed by browsers. OData content is consumed by Excel, Access etc. AtomPub content is consumed by publishing/blogging/etc software. GData is a fun one: it is (was?) used as a foundation of traditional API clients.
Another assumption, but perhaps you're expecting hypermedia to replace something else? You're mentioning "WSDL, OpenAPI and friends". Well, those are perfectly fine, and they're orthogonal to REST and hypermedia. GData is a good example: Google APIs used GData as a foundation, but actually needed extra documentation and extra code on top to drive users to the correct endpoints.
The "discoverable" advantage of hypermedia APIs does not mean that applications should be intelligent and discover how to use the API just by accessing it. This is possible, don't get me wrong, but there will be massive constraints: either you build HTML/CSS/JS to allow arbitrary apps, or you have a simple tables app that consumes ODAta. If you want a fancy iPhone app, you'll have to start hardcoding a lot of assumptions into the app.
The H of HATEOAS means hypermedia, a term created by Ted Nelson in the 60s. It's related to hypertext, which is the HT of HTML and HTTP. HATEOAS/REST is about creating hypermedia APIs, including HTML/HTTP. This means rich context, like Wikipedia, a database, or a Website.
Not everything matches this. The app I work on doesn't. And that's completely fine.