I'm getting 60fps with a 3 year old machine and an ATI HD2600XT which was a 100$ card when I bought it.
Enough CPU/Ram solid Motherboard, and any reasonably good card with 512 mb of ram should set you up.
Take the time to truly research what cards are good, which are great and which are great but cost 3x as much as the rest.