At the risk of butchering the concept for the sake of simplicity:

In a HATEOS API, clients need to know exactly one entry point endpoint. Nothing else is hardcoded. There is no Python code that happens to know "if you want to add a widget to a product, you POST to /product/$X/widgets". The API itself tells you where to go.

An acid test: assume your API entrypoint is /api. If your API keeps HATEOS kosher, you could in a serverside update change every other URL endpoint in the application without breaking clients, because the clients would be getting those URLs from the entrypoint URL dynamically anyways.

(That's not really the point of HATEOS, but it's a side effect).

There is nothing wrong with simple HTTP APIs, and a lot wrong with explicitly RPC (verb) oriented APIs in general, so adhering to REST principles isn't an absolute good.

This might be the point where 'dragonwriter tells me I, too, have misunderstood HATEOS. :)

One thing that's always bugged me (in a small way) about REST is that proponents/experts always insist that REST does not rely on any specific protocol (HTTP) but all discussions of REST carry a very strong assumption that specific actions are mapped to specific HTTP verbs. For example, Martin Fowler's doctor appointment scheduling example gives you "discoverable" hypermedia links for canceling and editing appointments, but they use the same URI and there is an implicit assumption that the client knows how to distinguish between the two by choosing the appropriate HTTP verb. It just seems kind of strange to say, well, REST isn't tied to HTTP, it's tied to any request/response protocol where each request is bound to a specific URI and one of these core HTTP verbs. Wouldn't implementing REST on any other protocol look an awful lot like tunneling HTTP over that protocol?

Another small gripe is the notion that a REST client need not have URIs to specific resources/actions hardcoded in them. The fact that you don't hardcode the specific URIs but rather a bunch of link strings that you then use to look up URIs makes this a lot less interesting. The way it's described generally makes it sound as if there is some kind of magical mechanism by which a client actually learns of the existence of a given endpoint, which would truly be magical. Really, all that's happening is that a client knows a name for a specific endpoint that it's looking for, and the API provides a way to look up the specific URI for that endpoint. Makes things tidy, but it doesn't seem like a feature that has much practical impact if you follow a "URIs shouldn't change" philosophy anyway.

Without breaking clients permanently. Running clients would not be able to continue their current interaction.

Yeah, I was just about to go edit that. "Cool URIs don't change" and all that. It would still be bad to change URLs; you just wouldn't need to update the client API code.