SUGGESTIONS: Server for PHP project

I just started in a porject in a company, they had it hosted on Google App Engine and the app was developed in Java. The thing is that this code was toltally unreadable. So i've came to the conclusion that the best solution would be start it all over.

Because it is a Facebook App, the logic would be stop using Java and start using their available PHP SDK. But, Google App Engine still doesnt work well with PHP, we cant install Frameworks like Yii without workarounds and etc.

So i think the best solution would be change the place that we are hosting the application. It needs to be a host for scalable PHP applications.

I've researched a little bit and found people talking about Pagoda and appfog

Do you guys have any suggestions? What is the best solution considering: Price, efficiency and also it needs to be easy to use. I dont have a lot of experiences managing servers, i usually have someone on the company that takes care of all of that for me.

Thanks guy, any help would be appreciated