Are there any good examples out there of services that implement that last level? I have seen and used the others but not discoverability.
Since their core product is an API, they've done a really good job building in all the levels of REST discussed in the article, including discoverability.
This article makes things out to be more complicated than they actually are. Just make decent HTML. REST was extracted from the web, it doesn't need to be imposed on it.