Really the amount of ram is probably the most key part here. It really depends on if you are intending to run vanilla minecraft or bukkit (or maybe canary). If you do use either bukkit or canary instead of vanilla then it comes down to how many plugins you are planning to install.
For most users a 2 core setup with 1GB of ram will likely be plenty. Minecraft itself limits to a single core for the most part but the second core will be useful for the additional thread of tasks that tend to run on bukkit or canary.
I personally have a 4 core VPS with 4GB ram but the only reason is due to the fact that I use the VPS itself for more than just Minecraft. I use it for other misc tasks that are done better remotely than locally with an appropriate nice level. The host uses Xen PV so while I may be isolated in my own playground I still keep other customers in mind. So far no complaints.
Oh and please stay away from OpenVZ. It plays horribly against Java (this is from experience). It limits against allocated ram and not used ram. Xen limits against how much is actually being used. Java always allocates it's entire heap when it is started.