Far be it from me to question Fred Wilson, but I actually believe he is not referring to an API, but is referring clean URLs.
The reason I think this is because the second half (of the two sentences) on the RESTful section says "...every resource on your site needs to have a URL and ones that people can understand". Additionally, there is another section for APIs called "programmable".
Seems like a minor misnomer, but still a good point.
People who have never used a diversity of web APIs (>= 20) should never be allowed to design them, or I will personally fly to their dungeons and strangle them with their own lousy documentation strings.
Test your "API" with a variety of languages, that are not C++ clones. If you can respond with a header value, don't make me parse a body (i.e. responding with 200 when the body says "error".) Accept whitespace liberally. Space should mean \\s+. Not just a particular " ".
Version your API. Don't obsolete stuff willy nilly. Even if you're clueless, it's not too hard to run three instances of the endpoint app, and route requests to a per-version instance with URL rewriting proxy.
Anybody who has ever sat in the specification committee of a "microformat" should never EVER be allowed near APIs that others might use. Specification-creep is real; one draft spec by 3-guys in their dorm room creeping into another spec by some other guys. I can cope with IETF and W3C pulling stuff out of thin air, but I will NOT tolerate being told to read several draft-0.01a.txt specs from 2003, for a myriad of "social identity" crap that no one, but those whose name appears on the first page, cares about.
Also, offer a sandbox, and dummy instances with mock data. Otherwise I will rape your live servers in a tight, unrolled loop (Srsly, I am on a fat pipe, running native x64 code; your instance of Jetty or WEBrick will never know what hit it.)
And also, for the love of all that is holy, when you offer a sandbox and test data, give me a way to deliberately trigger error responses.
It's all well and good to give me an is_test parameter on your payment API, but if using it causes you to blindly approve all payments, I can't test all of the code paths dealing with all of the possible failure modes(true story).
Last client, travel biz, had APIs to many holiday and travel co's APIs. Some of the big ones, no names, had no mock data. Being travel data, live data changed by the second. Had to employ someone specifically to fix test data, and the tests, simply to allow the devs to work. Insane.
Corollary: The reason the travel industry is such as mess is its complete lack of understanding of, and refusal to engage with, its customers. It's really, really easy to fix, but the suits refuse to acknowledge the problems.