So I need to get a VPS/cloud server of some sort - any recommendations?

It's mostly for basic, personal web projects (about 3.5GB worth of old photos and video) that won't serve a ton of traffic, but I also need to experiment so that I can:

Be more knowledgeable about the various solutions out there.
Automate all facets of server acquisition and maintenance: ChefPuppetCapistranoPHDmoonshine, etc. I want this thing to build itself, rather than to have me having to spend weeks configuring it and setting it up.

I know of:

Rackspace Cloud
EC2 (which probably won't work because of the persistence issues)

I don't need DNS hosting (already use DNS Made Easy), Email (using Google Apps), or any sort of webmin like interface.

I just need SSH, root access, Apache, MySQL, Ruby, Passenger, PHP (for old stuff), running on Ubuntu and that's about it - anybody got any recommendations?