<p>We don't exactly comply with the XML-RPC spec, but the concepts are nearly identical.  A client comes in over HTTP/HTTPS with an XML payload.  We respond with an XML payload answering the request.  This is primarily machine to machine, so no human to type a username/password.  Our construct runs within apache tomcat.  We would like to authenticate the request and since not every service is available to every client, we need to authorize the request as well.  We have both subscription and per use charging models so it is necessary to log everything.</p>

<p>What would you recommend for both server and client?</p>

HTTP BASIC/DIGEST works fine for most machine to machine tasks, and it handled by the server so your API is unaffected.
It doesn't work as well for interactive uses because it's difficult to "log out" the user without closing the browser.
Otherwise you'll most likely need to alter your APIs to include authentication information and have your methods authenticate that within your code.
Or you could use the classic "login", set a cookie, keep a session technique.
But, frankly, for machine to machine work, HTTP BASIC is the easiest.
edit, regarding comments.
HTTP BASIC is simply a protocol used to present the artifacts necessary for authentication, and it works well for machine to machine web services.
HOW IT IS IMPLEMENTED is dependent on you and your application. Using Java, you can use container authentication and that will provide authentication as well as role mapping. The user -> role mapping is handled in either a data file or database. The URLs protected, and what roles are valid for each URL, is managed by web.xml.
If you continue to add different roles to different URLs, then, yes, you'll need to redeploy that application.
However, if you're just adding new users, then you simply update your file or database. And if you're adding new logic, and this new URLs, then you have to redeploy anyway. If you have a ROLE structure with a fine enough granularity, you won't have to be messing with the web.xml until you actually add new methods. For example you could, at the extreme, create a role per method, and assign them individually to users. Most don't need to go that far.
If you don't want to use container authentication, then write a Servlet Filter to implement your vision of mapping user and roles to URLs. You can still use the HTTP BASIC protocol for your clients, even if you implement your own facility.
If you're looking for an overall generic Java security framework, I defer to google -- there are several, I've not used any of them. I've had good luck with container authentication and writing our own.