Halo is a tough game. My (now deceased) X800SE 128mb would sometimes stutter at 1024x768, while my friend's FX5200 would do just fine at 800x600.
I would personally go for the 7900GS. It offers a lot of power for only $140 after MIR. That card should be able to play Halo at HIGH at a resolution of 1680x1050. While resolution is nice, you most probably wont be able to tell the difference between 1280x800 , 1680x1050, and 1920x1200 unless you squint at the monitor the whole time.
So, from personal experience, I would suggest the 7900gs as a poweful and budget card that can be easily overclocked to 7900gt levels.
good luck