Choosing a VPS solution for CiviCRM
Most recent installs I have done of CiviCRM seem to behave best with 2gig minimum of memory.  1.5gig should work as a minimum, but memory is cheap so go with 2gig.  

We typically use eApps for most of our clients. They have a nice interface to easily adjust your resources up and down as you need: memory, cpu, disk space. Being able to easily raise and lower these resources (and just pay for the days used) is really nice, for those times you are importing or exporting or doing some other resource intensive tasks. They also have a relatively great support desk.