$700 computer (was $650, damn the refurbished parts not working!) and I run HL2 at almost 100% max (not playing AA all the way up, I believe), get over 50fps constantly (only drop was in gmod with 200 explosions on screen).
Oblivion, playing between medium - high (with VERY high above high) and I get between 20 - 40fps depending on how big the town is.
FarCry, MAX settings on EVERYTHING but resolution (1024xwhatever) and I only got 1 drop (and that was pretty random, but it lasted 10 seonds max I believe)
The only problem is, if you go with less than medium now, in a year I'm thinking you'll regret it. And I said exactly what you said, Tiberium. EXACTLY. "I don't need graphics, it's about gameplay"
Now, I'm not Jonsee, I'm not Yoshi, I'm not CM, but my limited computer knowledge (and a thread I made about building a $500 computer as opposed to $650) is telling me that you'll get low settings in most of these games, and it'll be outdated pretty soon.
I have an AMD 3000+, and I think that'll be the first thing I upgrade because it's starting to be the bare minimum. And that'll be your budget if you go with $500. The extra $100 - $150 will be worth it.
I had a blog. It sucked.