6800GT's are definetly the way to go, well if you can afford it the 7800GT or gtx's are extremely nice!
But the new Raedon X1800 series are pretty much on par with the 7800GTX's and in some respects.. better.
If you are going to replace MB, get rid of that tired old P4. Either go with socket T (New Intel) or even better, go with an AMD A64. For one it is 64-bit ( a year from now it WILL matter) and also because AMD has taken the memory processor off the MB and put it on the CPU. You will also want to go with the Socket 939 AMD. Socket 754 is (will soon be) entirlly Sempron.
i was thinkin...
GIGABYTE GA-K8N Pro-SLI mobo---> 108
AMD Athlon 64 3200+ Venice ------> 190
then he'd be toly set for the future too_____
and be more than pimp for now------> ~650
or else just get the 6800GT, but then hed have to do more upgrading in the future
but still, trashcan is your best option.