At ShareLaTeX (https://www.sharelatex.com), our hosting costs are around $1500/month (can probably be doubled once you add in backups and other supporting services). This is for a similar service (LaTeX is just subset of what SageMathCloud does, but a resource heavy subset). However, ShareLaTeX handles orders of magnitude more traffic as far as I can tell. One of the big factors in a service like this is being able to get the cost-per-user down low enough that it's a viable business model given that a student/academic is not going to pay more than about $10/month and most won't pay at all.

One of the big wins for us has been using Docker to isolate projects. Sure, each project is resource heavy when run/compiled/executed, but if you have lots of users, they're probably not all resource heavy at the same time. The more lightweight the virtualisation/containers, the more they can share resources. It sounds like maybe each user is getting to hold on to too many resources that they aren't using, and so it's costing an order of magnitude more than if they could share all the resources perfectly?

I'd be happy to chat more about this stuff (almost all of the ShareLaTeX code is open source as well, except for the enterprisy stuff). We've also got a new project called DataJoy for Python and R (https://www.getdatajoy.com) which has similar scaling challenges that we've been working on.