I used to be a skeptic regarding web services, because I often found the examples given too complex or unconvincing. Stackoverflow, with its use of reCAPTCHA, OpenID, and gravatar, has changed my view. Their use is a showcase of web services that can simplify the deployment of an application by handling part of the required functionality, while also providing more value to the application than what could be achieved by embedding the feature in it.
What other web-service-based application building blocks would you recommend? Ideally, I'm looking for services that are simple to use (RESTful), freely available, reliable, value-adding, and that can be setup with minimal negotiation with their provider.