I was able to put AA to X4 on CoD4 on 800x600. It looks and runs great.
Haven't tried with higher rez yet, mainly because 800x600 looks perfect my my MBP to me.
From what I've read and my limited experience, it's best to first max the resolution, then apply AA, as a higher resolution will have a more significant impact on visuals than AA, especially when you're running at such an low resolution--very low! In COD4 (Mac version) for example, running at my native res (1680x1050) renders a hugely superior looking game than at a lower res with 4x AA. Of course that also means you'll have a much easier time spotting other players in multiplayer, as the tiny little dot that is their knee will appear clearly as that in sniper scope; meanwhile, at a lower res, it's harder to distinguish between knee and all the other similar textures in game. Since you haven't tried it, I urge you to. So long as you maintain an above 30+ fps, I'm confident you'll prefer the visuals.