I think DreamHost ("DH") will suit you pretty well. They do daily backups automatically, and you can do any restore operation yourself, from either the dail/weekly/monthly backups as you wish. The backups don't include MySQL AFAIK, so for that you might want to have your own backup running. (The "how" is documented in the DH knowledge base.)
On the topic of your large user base, it would be worth figuring out if you would exceed the DH limits in terms of CPU time. Their SQL limits and bandwidth limits are insanely high so that will surely not be a problem for you. DH hosts many large sites so I would think that CPU is also not a problem.
Finally it should be noted that every host has occasional problems. DH just got hit by a massive DDOS attack which lasted a few hours, but in the years I've been with DH that has "only" happened twice. Apart from such events that you can't plan for, there have been complaints about sporadic email and/or website outages. I have not felt any problems, but then I host a few small sites, nothing big and nothing where a business relies on 24x7 operation. Have a look around in these forums to see those discussions (but remember that the masses that don't have any problems don't post here, so the forum might be biased more toward the negative than is reality). DH Support response time varies but they strive to answer within 24 hours. If you need immediate answers then get a hosting plan with callback option, otherwise be prepared to wait some hours for a reply. (That's not a problem for me, but others mention this.) Apart from the official Support, there's also these forums as well as a knowledge base and a wiki, each of which is a source for help from customers.
Overall, I myself am extremely pleased with the services, terms, and prices of DH's hosting plans. You could simply try it out and see if you like it. There's a 97-day money back guarantee (that works, no questions asked), so you're not risking anything -- except the time it takes you to try out stuff here, when you only have one month to switch. You could use that time to play around and configure everything here so you can do a quick swap when you decide it works.
[color=#CC0000]Get $50 off[/color] with promo code "LESS"! See here what else you get!