I was totally hooked on Need for Speed Underground and Colin McRae Rally 2 when they came out - such great games.

Get something that does DirectX Shader Model 3.0. The GeForce 6600GT is still a very good choice and recommended by many. You're looking at 100 quid though. It is a lot from a money point of view, but in my opinion you're missing out if you downgrade, and if you upgrade the price/performance ratio is too steep. IMHO it is the sweet spot at the moment.

As for Linux compatibility, the nVidia card would require the closed nvidia module, which works ok. ATi cards work well - my Radeon 9800 Pro does direct rendering out of the box in Ubuntu.

Pretty much everything should have DVI - if there is no DVI, something is very wrong. 500W should be fine for your rig. I'm running a ~400W Sparkle power supply on my overclocked-to-XP3200+ machine with bells and whistles. The graphics card would just have a molex on it, so there are no other new standards or plugs for it.