After I got really annoyed with current services for backups, their custom programs and limitations, I've started my own 'company' offering this sort of service.
I've designed a page myself over at http://www.royalbackup.com/ where I'm offering the service. I'm not selling small allocations since it would be a hassle to deal with too many customers for a few bucks.
More info is available on the site, and you can e-mail info@royalbackup.com for a free 100mB trial account for 7 days to take it for a spin.
Any opinions or suggestions are more than welcome.
More info: Public service has only been offered since yesterday, but I've had the service running for a while. Current uptime for bishop is >60 days, though it does get taken down from time to time for regular maintenance (security updates and such).