As long as you don't mind the tiny monthly charge, I've found Jungledisk to be rather good. The key thing is that it does de-duplication and in a really smart way. For example, if you backup a complete server backup in the form of a .gz.tar file one week, then do it again the next week, great deal of those two files will be the same. Jungledisk notices this, and will only backup the chunks that are different. Your S3 storage use then becomes much, much less than it might otherwise be AND your backup times are vastly reduced.
It does hammer your disk when it is updating its internal databases and things though, so you will see a bit of a load spike when you use it.
The code has not been updated for years though, and it doesn't seem particularly high on the RackSpace priority list. Don't let this put you off though! It has worked fine for me - so far!