On the AMD side, I think everything above a Sempron is safe (but I'm no expert and you'll have to check).
On the Intel side, the 6XXX, 8XXX (dual core, the future 8XXX quad core won't have them) and 9XXX have virtualization extensions. Avoid the Celerons, 2XXX, 4XXX and 7XXX.
Phenom is a good choice if you want to support AMD. They require more power than their Intel counterparts though (and Intel is also good towards open source). The processor prices won't really differ for the same performance (unless you want virtualization instructions on sub 100$ processor), Intel will have lower power requirement (just compare real power usage, not TDP), AMD on the other hand has really good sub-100$ motherboards (similar Intel-based motherboards are more expensive), so both choices can be great depending on your usage.
AMD and Intel gains in 64 bit mode are about the same (a bit more than 10% on average, something like 12-15% on common applications, at least in Linux).