One of the great benefits of virtual servers - is that they're virtual. Meaning you can easily scale up memory as and when needed. Try and go for a provider that allows you to do this, that way you can start with a smaller VM and scale up once you find you need more memory.
If the provider you choose doesn't allow you to scale up on the fly try and make sure your server is as easy to rebuild as possible (I'd recommend using a configuration management tool such as puppet) and that your applications are easy to deploy so moving providers or packages is minimal hassle.
Once you purchase a VM install a performance monitoring solution that will allow you to see your resource usage and history so you can plan for the future. Certain providers will do this for you (one of my favorites is Linode) for those that don't theres solutions such as Cacti, Collectd, Munin, Ganglia etc
Its hard to give you an exact figure as all sites perform differently and you didn't mention in your original post what sort of sites you're running and the content they're serving. I'd say a general good starting figure would be 512MB however.