I know that my Googling skills are failing me because there must be something like this: a simple, easy-to-use remotely hosted directory service (and even better, exposes the user directory through several different interfaces, and SSO).
Do you know of one and/or have one to recommend?
I am looking at Atlassian Crowd - http://www.atlassian.com/software/crowd/overview - which comes close with the pluggable interfaces, but it does not implement LDAP. It can only connect to an existing LDAP server.
Answer
This has already been discussed on ServerFault, and I think the answer given here may be a good starting point for your search. It lists Symplified, Entic.net and eApps.