The only difference between REST-in-practice-today and WSDL is that you aren't expected to map each network interaction to a single procedure call. This makes a number of things easier: cache the results, GET data across many different endpoints if you know the format, enable data and metadata extensibility through the payload, and follow hyperlinks if you know the link relation and target format.

The Facebook Graph API is a great practical example of this ease of use in practice: https://developers.facebook.com/docs/reference/api/

You're quite right that things like "related" and "metadata" link relations mean nothing if you don't know what those mean - they are hooks for future bits of agreement. The difference between REST and WSDL in the long run, in my opinion, is the practical composability of small bits of agreement (or specs). The Web Services stack (SOAP, WSDL, WS-*) has had a very difficult time composing a bunch of specs together as the kernel of their agreement is basically the XML Infoset. With the RESTful Web, the kernel is HTTP, URI, and MIME (for now), which has endured a number of extensions (Flash, HTML5, Atom/RSS, etc.) and evolutions (the rise of mobile devices).