I've found that my Ti4200 struggles more with AA enabled than with AF enabled... Playing Halo with 8xAF and a 64mb Ti4200 at 1024x768 provides playable framerates about 85% of the time (massive explosions in the hangar area of the Truth and Reconciliation produce the lowest framerates, though I'm not entirely sure why an empty hangar gets such low framerates), but that's with an Athlon XP 3200+ and a gig of Mushkin at 2-3-3-11...
My vote for "most performance lost for least visual quality gained" goes to AA, the ultimate waste of resources. I run 8xAF in OpenGL, and 64-tap AF in DX (64-tap being equivalent to 8x, I assume), with virtually no performance loss, even at stock frequencies.