Document versus RPC is only a question if you are using SOAP Web Services which require a service description (WSDL). RESTful web services do not not use WSDL because the service can’t be described by it, and the feeling is that REST is simpler and easier to understand. Some people have proposed WADL as a way to describe REST services.
Languages like Python, Ruby and PHP make it easier to work with REST. the WSDL is used to generate C# code (a web service proxy) that can be easily called from a static language. This happens when you add a Service Reference or Web Reference in Visual Studio.
Whether you provide SOAP or REST services depends on your user population. Whether the services are to be used over the internet or just inside your organization affects your choice. SOAP may have some features (WS-* standards) that work well for B2B or internal use, but suck for an internet service.
Document/literal versus RPC for SOAP services are described on this IBM DevelopWorks article. Document/literal is generally considered the best to use in terms of interoperability (Java to .NET etc). As to whether it is easier to support, that depends on your circumstances. My personal view is that people tend to make this stuff more complicated than it needs to be, and REST’s simpler approach is superior.
As mentioned it is better to choose the Document Literal over RPC encoded whenever possible.
It is true that the old java libraries (Axis1, Glue and other prehistoric stuff) support only RPC encoded, however in today’s most modern Java SOAP libs just does not support it (e.x. AXIS2, XFire, CXF).
Therefore try to expose RPC encoded service only if you know that you need to deal with a consumer that can not do better. But then again maybe just XML RPC could help for these legacy implementations.
BiranLy’s answer is excellent. I would just like to add that document-vs-RPC can come down to implementation issues as well. We have found Microsoft to be Document-preferring, while our Java-based libraries were RPC-based. Whatever you choose, make sure you know what other potential clients will assume as well.