If HATEOAS implementation was more widespread the biggest advantage would be the ability to create standard libraries for API calls rather than thin wrappers for every language. Your API would also be more or less self-documented, hopefully making it easier to navigate for humans and machines alike.

I am curious as to why this can't be handled at a HTTP level with OPTIONS? Could I not OPTIONS query a URI, and receive a list of supported HTTP methods (GET, POST, PUT, etc) that are available on this resource?