One of the things I like most about hypermedia is that the hyperlinks can represent a complete set of functions which can be applied to an object. In other words, each object contains its own method list. This fits well in languages which get to implement catch-all methods, like Ruby, and I couldn't resist coding up a client that worked that way.
(There's room for this sort of trickery in near-future ECMAScript too, with Proxy[3]. I would really like someone to do this and I would kind of like it to not be me.)
When you lay out your API according to that philosophy, and cache a few "stepping-stone" objects you'll be traversing often, hypermedia APIs don't seem so inefficient at all.
As to your last point: take a look at HAL[4]. It sits alongside a "traditional" API layout very nicely, essentially adding "_links" and "_embedded" which can be safely ignored by non-hypermedia clients. The HAL spec is extremely sane.
[1] https://github.com/codegram/hyperclient
[2] http://weluse.github.io/hyperagent/
[3] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
