It's got a PCIe slot. The current 6600 is a PCIe. So anything above a 4650 to 4670 is a waste of GPU then? Should I go with 512 or 1 GB?
Also, how much boost am I going to see going from the GeForce 6600 to a Radeon 4650 or 4670?
You'll see more than a 100% boost probably. Grab an HD4670, and a 512Mb version.
There is not huge difference in prices between the two TBH, so yes, grab a cheap HD4670, but do not be afraid of the 1Gb cards, that said, do not pay more for a 1Gb card either, the HD4670 is just not fast enough to use all that memory.