Right now this blog is hosted by powerVPS, which provides virtual private servers. This is to say they have a large powerful box, and they run virutalization softare (Virtuozo) which allows several users to have the illusion of a private machine, on which they are the root user. In theory users get an equal share of the machine, but since most of the users do not run at full capacity, any user can "burst" to temporarily use more resources.
Unfortunately I have found that this approach does fine with CPU, but not with RAM. The virtual server I first used had 256MB of ram (burst to 1gb) available to it. But it was not able to perform at the level of a dedicated server with 256mb of ram -- swapping the rest to disk -- would do. It also doesn't perform anywhere near the level of a non-virtualized shared server, which is what you will commonly see in very cheap web hosting. An ordinary shared server looks like normal multi-user timesharing, though they tend to virtualize the apache so it looks like everybody gets their own apache.
I eventually had to double my virtual machine's capacity -- and double the monthly fee. You probably saw an increase in the speed of this blog a couple of weeks ago.
Now the virtual machines out there are pretty good, and do cost only a modest performance hit when you run one. But when you run many, you lose out on the OS's ability to run many copies of the same program but keep only one copy in memory.
I propose a more efficient design that mixes shared machine and virtual machine concepts. One step to that would be to not have every user run their own mySQL database. MySQL takes about 50mb of ram, which is not much today but a lot if multiplied out 16 times. Instead have one special virtual server (or just a different dedicated machine) with a copy of MySQL. This would be a special version, which virtualizes the connection, so that as far as each IP address connecting to it is concerned, they think they have a private version of mySQL. This means that everybody can create a database called "drupal" (as far as they think) if they want to. The virtualizer would add some prefix to the names based on which customer is connecting. This would also apply to permissions, so each root user would be different, and really only have global permissions on the right databases.
You would not be able to modify mySQL's parameters or start and stop it -- unless you went back to running a private copy in your own virtual server. But if you didn't need that, you would get a more efficient database server.
The bad news -- it's up to the hosting companies to do this. MySQL AB doesn't get paid by those hosting companies, so it's not particularly motivated to put in changes for them. But it's an open source system so others could write such changes.
The other big users on web hosts are apache and php. There are many virtualized versions of apache, but this is often where people do want to virtualize, to run custom scripts, java programs and special CGIs. Providing a mixed shared/virtual environment here would be more difficult. One easy approach would be to have it be two web sites, with some pages on the shared site and links going to the virtual site. More cleverly, the virtual apache could have internal rewrite rules that are not shown to outsiders that cause it to fetch and forward from the virtualized web server.