I have an iMac G5 single 1.8 Ghz and I could run it on full settings without any problems. I played it with only the hardware it came with, too. (256 RAM, 1440x900 res, etc.)
Maybe I missed it, but have you tried the latest version, 1.05? When Halo was first released High and Extreme Lens Flares caused performance hits due to the method used by the developers. Coupled with FSAA it made a huge performance hit. With Mac OS X 10.3.5, the necessary feature to support hardware accelerated Lens Flares was added to Apple's OpenGL implementation. The latest version of Halo has the code in place to take advantage of the new feature so you should see almost no performance hit with High and Extreme Lens Flares and significantly less of a performance hit when coupled with FSAA.
Also, Radeons, even the X800, can only do 2, 4, and 6x FSAA. The other numbers are for NVIDIA cards. I'm not sure which sample rate ATI cards fall back to when you set it to a number the chipset doesn't support.
I've had a Mac Halo Performance page setup for a long time:
but it only includes information up to Mac Halo 1.05.3. I still need to update it with the Mac Halo 1.5.1(IMO, should have been named 1.06 to cut down on versin number mistakes. Too easy to confuse with a 1.05 version) updater information as that version includes the Lens Flares fix.
Also, any version newer than Mac Halo 1.02 requires the CD in to play.