Even a 8800GT can handle high settings at your resolution. There are AGP and PCI cards getting enough performance for low settings on that first benchmark. I didn't spend too much time searching, but I'd say a 250 would work by what I did find. Even a 220 would likely be enough for low settings. Keep in mind that your CPU also has an effect.
You may be different than me, but in no way shape or form, would I consider 25 FPS playable. Playable FPS is 40+ for me and many people I know. With anything lower, a great deal of people get motion sickness.