I only recently properly grokked this. Discovery isn't necessarily the point, although it's nice. What makes HATEOAS essential for me is that if you start with the assumption of HATEOAS, you can add functionality in the form of new links at the server side without breaking existing clients. Yes, there are other ways to achieve this, but HATEOAS is an excellent way of getting it for free.