Just keep it simple..that's the most important thing. Simple POST name/value pairs and JSON output. I don't care if it's technically REST or not. One big long document describing every call and response (makes it easy to search with CTRL-F). Lots of examples. Complete example code. High level libraries that implement the boring parts. A direct email address to the developer.
Twilio's REST API (http://www.twilio.com/docs/api_reference/REST/) is really easy to understand, very sensible. It's practically self-documenting, but it's backed up with thorough documentation and examples. One can get up and running very quickly because of that. They have clearly spent a lot of time getting the API right.
Paypal has one of the worst APIs I've ever used. It's a useful model of what to avoid, particularly its multiple formats and its flakey and often outdated sandbox testing servers.
Take a look at Friendfeed's API V2 (http://friendfeed.com/api/documentation). Not only does it use very intuitive RESTful architecture, but it also has very awesome documentation and libraries.
Of course, now that they're with Facebook the developer support will likely not be as good, but the API is great as it is regardless.
It's not a web service, but I always thought Qt had one of the best APIs out there in terms of style, consistency, and documentation. It's worth looking at just from a packaging perspective.
Amazon has the most useful APIs out there. Don't copy them though.
So many small companies put out giant behemoth APIs with crazy security hoops because that's what Amazon does and Amazon's stuff is really cool. As a result, nobody outside the dev team can figure out how to authenticate, so nobody actually uses the API.
Check out Twiddla's API (http://www.twiddla.com/API/) for an example of how to keep things lightweight. 2 POST endpoints and an IFRAME syntax. Only the bare minimum security, and a huge emphasis on getting your thing up and running without having to sweat the API.
I suggest taking your time when you implement the first version of your API. Nothing is worst than developing based on a rushed v1 API, which later gets modified without you knowing. No one wants to be caught calling a deprecated function that then gets removed.
Furthermore, try to keep all of your API libraries up-to-date. For example, I was almost driven crazy by Google's v1.0 Python Spreadsheet library's lack of support for insertion based on case-sensitive row names (See http://code.google.com/apis/spreadsheets/data/1.0/developers...). There is no documentation regarding the requirement that the row name must contain only lower case characters. The .NET library is v3.0 and appears to offer much greater support for this type of basic functionality.
Provides a lot of functionality.
Basically anything you can do on the website you can do through the API.
The names of the calls are intuitive.
Provides different formats.
And most importantly has libraries available for different languages that will make the calls for you.
