That doesn't look like an AA problem to me. How are those stairs built? Are they a single mesh or seperate meshes stacked? If they are stacked, I'd give the BSP algorithm and Aggressive optimization a try. Both of those are for use with complex scenes w/ clustered and/or overlapping objects. The 48-bit dithering might help too, because that is used for removing color banding... 'Evening skies' is the example used in the manual where it might be good to use dithering.

The attachment shows settings that I used a little while back successfully for a very complex render.

Friends don't let friends use booleans.