I'm a PHP developer and I've made something I want to push live.
It requires memcache, and I'm expecting a fair amount of traffic, at least at launch, so I'd like it to be fast.
I'm really awesome at programming, but when it comes to getting hosting stuff set-up (other than run-of-the-mill shared hosting) I lack experience.
Joyent might be a good solution for you. Honestly adding memcache to a LAMP stack is ridiculously easy and you should be able to do it with relative ease. Find a good VPS provider (linode and slicehost are so good I'll recommend them without my referral code) and you should be able to just apt-get install memcache.
To get a more specific answer though, you really need to quantify how much a 'fair amount of traffic' will be. For some people a hit a second is a massive, for some people 300 h/s is cake.
If you need a hand, email me, I'd be happy to help