I would argue that you don't. JSON isn't a format for HATEOAS, for the reason you state. I'm leaning towards saying HTML 5, with some of the new semantic markup

I would argue that you don't. JSON isn't a format for HATEOAS, for the reason you state. I'm leaning towards saying HTML 5, with some of the new semantic markup, though it's not perfect. You can use both, and simply use the Accept HTTP header to determine which format you want. It gives you both discoverability of HTML (with <a>), and data transfer that is easy to parse.