Depends on the internals. If you under clock a 5870 to 600MHz its still going to blow away a 4870 at 750MHz, architecture and core count makes a much larger difference than the speed of the GPU. The memory only comes into play at higher resolutions, 512 is fine up until you hit 1920x1080, at which point 1GB gives a slight advantage.
What two cards are you considering? Link to them if you can.