i use site5 for most of my stuff because i've been with them since 2006, but i think linode is the preferred VPS provider these days on both price and reliability (can't speak to their CS but i hear it's good from the WHT forums). site5 managed VPS servers are a little expensive though the CS is top-notch from my experience
given the experience you have with server admin i'd go for a managed VPS with a control panel that does simple point-and-click installs of scripts or services. and the CS to install/walk you through most stuff that is supported on their servers, like APC, memcached, or whatever else
i assume it's poorly written because it makes way too many database calls; php is pretty hard to screw up too badly in most other cases to be honest. (unless you are doing large simulations or something; i recently rewrote some monte carlo simulation code i had that was doing probably 8x more CPU-specific work than it needed to be doing, lolz) i highly doubt you're going to be bound by cpu if it's a basic application / site to view with that many visitors but i guess i could be wrong; someone could have done something seriously wrong. and in that case you should be caching expensive and commonly called resources. probably using memcached but possibly with a different persistent data storage engine like mongodb or whatever (i use mysql in a standard RDBMS setup as well as a novel NoSQL solution
detailed here).
anyway that is probably too much detail for a general solution. if the php app is choking the server due to disk i/o (most likely scenario) then rewrite the database classes and introduce resource caching if need be