I wouldn't necesarrily put the Cloud options above standard boxed setups, but thats about right. And from your questions, the "deal" with managed hosting is something you are going to want. Basically that means they take care of your box, they do updates, they fix problems and down time, etc. Good managed hosting is worth it's tech's weight in gold.

At that level, I would suggest a basic to mid sized VPS, which should give you enough memory to run the backend a wordpress site needs for that many users and plugins. Shared hosting would work fine if you were to use something like my system (uglyhost), because I limit the amount of users/traffic per box, but most services like GoDaddy and the Blue guys just stuff in 60-70 accounts per box and you can get some nasty spikes, bad DDoS hangovers, and much more from service like that.

If you want to have your own box on a managed solution, I would suggest WiredTree. I run 3 dedicated servers through them right now, and their support is just amazing. I never have to worry about going out for the weekend and my sites coming up empty or my database not backing up (woe to the days I didn't do backups). They have a slightly higher price tag than the big 3 hosting companies, but I the extra $10 a month is worth it for the 20 hours a week I don't have to spend on each server.

I would call them as different types of hostings, here are the main distinctions:
Shared Hosting - Very cheap + limited resources, could be banned if you abuse the resources

VPS Hosting - More expensive + more hardware resources (disk space, memory) compared to shared hosting + (generally)technical knowledge required

Dedicated Hosting - Even more expensive + you rent the whole server + (generally)technical knowledge required

Cloud Hosting - More expensive + highly scalable, best known for its ability to handle massive amount of web traffic

Managed Hosting/Service - There is no standard way of defining this but, generally you need to take care of the server yourself when it comes vps hosting/dedicated hosting etc. With managed hosting/service, you get a server guy at your disposal, to do things like server monitoring, backup, maintenance work, etc.

If you just start to launch a site, I suggest to go for shared hosting to save some bucks. When the traffic increases, you can switch to vps hosting. Try to pick up some basic server knowledge or just pay some money for server management if you want to.

I always recommend approaching this from the business side not the tech side. If you are confused about hosting, then you may need a true IT partner rather than a turn key service.

Ask yourself these questions:
- Do I know how to apply a server's security patches?
- Do I know how to update Wordpress?
- How much downtime can I tolerate?
- If things hit the fan, how easily can I recover?
- How much will an outage cost me?

I try to get clients to focus on the big picture. Once you know your capabilities than you can look for a host that fits your needs.

Companies like WP-Engine focus just on wordpress. VPSDotNet has good VPS services but you have to update things. Managed service providers may provide full scope support.

In terms of size of hosting required, this really depends on your site's plugins, themes and design. I've seen simple sites run on tiny VPS while complex sites require clusters.

For example, I have a client with a site pushing about 1 million pv/mo. They use a single low end server. I have another with 35 mill pv/mo. They use a cluster with a dedicated database server, web server and content delivery network.

keep it simple:
shared (many clients use same server)
vps (fewer clients use same server)
dedicated (you are the only one to use a server's resources.)
cloud (for scalability. if your traffic increases so is the number of 'virtual servers' to face the traffic)

Shared -> VPS -> Dedicated -> Cloud