I am looking to downgrade from a dedicated to a VPS server (several, to spread it out) and was wondering if 512MB will do? I have Boost with all core caching enabled, and mostly anonymous traffic.
It depends on a number of factors:
What contrib modules are you using? The bare minimum Drupal needs to run is 32 MB, but that truly is the bare minimum. Contrib modules and doing anything moderately complex with code will increase your memory requirements. While you're using Boost which is great, you still need to generate the cache, which requires RAM. But unless you're doing something really intensive, I've found you can generally be fine with 128 MB for PHP.
What web server are you running, and what type of load are you expecting? If you're running Apache with its default settings, it'll eat up a lot of memory: generally 128 MB or more. Optimizing your Apache environment or switching to a less memory-intensive server will free up more memory, but it's up to you if that's something that's possible.
Are you running your database on the same server? MySQL has its own memory requirements, and you'll find it takes up the bulk of a shared server's memory. You'll bump up to the memory limit on a small VPS pretty fast, especially if you're running InnoDB or have a large site. The general recommendation is somewhere between 70-80% of RAM should be allocated to MySQL running InnoDB, which is ~360 MB on a 512 MB instance: not a lot of room for PHP and Apache (or anything else).
Are you running any other service on the same server? If you're running Memecached, Varnish, APC, Jenkins, or any other service common to a Drupal environment, they all take up memory, and in many cases, a lot of memory.
If you're running a small Drupal site with an optimized Apache configuration, database on its own server, and no other service, I've found 256 MB to be the bare minimum. 512 MB is okay, not great, if you need to run the database on the same server and want to enable APC, but you still be looking for ways to save RAM.
I personally run the database, caching, and continuous integration services on other servers and use a Micro EC2 instance (613 MB RAM) for most Drupal installations I do. But I'll bump that up to a Small instance (1.7 GB, overkill, but there's nothing in between) if the site's going to get a lot of traffic.