I finally got some good performance with Halo under 800x600 and 1024x768 avg any where from 60-50 FPS and getting as high as 83+ at times.
My Specs:
P4 2.0a CPU
1 Gig 2700 DDR
Radeon 9700 Pro
Audigy
Catalyst 3.7
What I had to do:
1. Under XP display Settings, under direct3d tab, put the slider on balanced. On AA and AF select App Preference. On Text pref put it on high quality. Mipmap put on high quality. Wait for vertical sync should be put on always off. TruForm I put on App Preferece.
2. Under Halo, I have all options on high and turned on. I have NO VSYNC selected in Halo as well (but selecting VSYNC shouldn't be a problem). Refresh Rate is set to 70 or 85 if your monitor can handle it. The resolution in Halo you can start with either 800x600 or 1024x768. In Audio, I have High and Hardware Accelertaion on.
3. While playing Halo, access the console and type rasterizer_fps true
This will show you on the screen your FPS and the average. Don't use the TIMEDEMO as that is a complete waste. With these settings, I am playing with no slow downs and it looks silky smooth. Enjoy!