I've been happy with a small installation (1 "server", 10 or so clients) of
Bacula. Meets all of your requirements *except* that adding a new client requires access to both client and server. I'm not aware of any systems that don't. (There are Windows systems that fake by creating a default share of every disk when creating the client system, but that seems like a bad bad idea to me.) Bacula is true client/server - the WIndows client knows about all the Windows specific stuff needed to do correct backups, ditto the Unix client.
(I quoted "server" above because the Bacula "server" is in multiple parts. Of particular interest is that the "Storage Daemon" can be multiple machines/arrays/tapes/whatevers.)
Initial configuation is non-trivial, but that's true of any system of this type. The Bacula documentation is quite good, though, as are the examples and the mailling list.[url][/url]