> The problem with me is my app will have subdomains for each user. For example, `john.myapp.com`.
Sounds pretty straightforward. Wildcard DNS entry, wildcard vhost -- two lines of text that say "point all DNS queries to the IP of my VPS, point all HTTP requests to this document root (your app)", then your app has some code that looks at the hostname in the request to decide which site to show. Subdomains are not 'things' that take up any resources.
> These subdomains are each going to be password-protected areas with healthy amounts of embedded video and I just don't trust the shared hosting I currently have.
If all the videos are embedded offsite, then they really have no impact on your choice of hosting solution. You don't have to handle the bandwidth or storage or even the HTTP requests for the videos. A shared host wouldn't know or care if you put a million videos on each webpage -- it would have no impact on their server. It'll have no impact on yours either.
> What do you think of something like this from MediaTemple: http://mediatemple.net/webhosting/ve/ ?
Considering it's an unmanaged service, I don't see why you'd pay them $30/month when Linode is only $20/month and has a perfect review record among HN hackers.