Most references I've read on web services talk about how important it is to design the granularity of the right - and it is. But, these references typically fall short of actually giving any useful advice about how to get it right.
While there may be no perfect answer - no cookbook that lets you get granularity perfect every time - there are a few guidelines that can help.
There are three key areas to consider when you are looking at granularity:
Performance and size
Transactionality and state
Performance and Size
Web services are accessed remotely. This means that there is significant overhead to making a round trip. Because of this you need to look at the design of your service and remove unnecessary calls. For example, don't make creation of a purchase order consist of "create PO template" followed by a call to "add line item" for each line item - have a single "create PO" service instead.
Some simple rules of thumb here are:
Combine (related) operations that execute in less than 5ms (because the overhead of even a simple "ping" is usually in the low milliseconds, you'd end up with a large percentage of the time taken up just because of the infrastructure itself).
Break apart operations (if possible) that take more than 5s to execute. This is usually a sign that you are trying to do too much at once. Operations that take this long can limit the amount of concurrent usage that your service can handle.
In terms of size, many web service implementations are constrainted in the sizes of messages they process efficiently. One reason is that the entire message is typically brought into memory, and so you have to consider the memory required to handle parallel calls. Typically, messages less than 1MB are safe. As you get above this limit, different implementations will start to hit their limits. So, think about what the sizes of your messages will be and adjust your granularity accordingly.
Transactionality and State
You should avoid designing a service that requires transient state to be maintained between operations. This not only impacts performance (by requiring the service to keep the data around between calls), but it also impacts failure recovery - what happens if one node in a cluster goes down? Another way to say this is that every operation should be self contained.
If an operation is going to change data, the data changes should be performed as part of one transaction (never more than one). The reason is that if a failure occurs somewhere after the first transaction completes, error recovery becomes very hard - especially when the expectation is that the consumer will compensate for any failures.
On the flip side, avoid putting too much into one operation. Let's look at the example of "create PO" again. While this might seem like a perfectly reasonable granularity, what about "create POs" that lets you create multiple purchase orders at the same time? This might seem reasonable (because there would be fewer round trips), but what it means, in practical terms, is that one PO can affect another - if there's a problem processing one of the submitted POs, all would end up being rejected.
Understand your business and you will understand what granularity makes sense - while this seems logical, many developers and engineers don't go the extra mile to understand the "big picture" of what they are doing. This is critical to achieve a successful service design.
That said, think about the granularity from the perspective of simplicity and generality. Strive for a single operation to fulfull a complete business task, and only add extra operations as is absolutely necessary. If making it simpler makes it more general (or vice-versa), then you are going in the right direction. If you get this right, then the opportunities for reuse of your service will increase dramatically.
The granularity of an individual service (operation) is one issue. However another, perhaps more complex and potentially painful is the granularity of your WSDLs. Some say one service/operation per WSDL. Others say create service bundles in a WSDL. The issue is one of maintanance versus versioning. Having one service per WSDL is great for versioning if a service recieves a change request, but maintaining all those WSDLs adds extra burden (assuming you have a lot). However, creating service bundles in a WSDL forces you to version more than the service that had a change request, thus affecting all consumers of that WSDL. Is there a right way? My guess is no.