Unfortunately, you will have to test all adjacent pixels, but I wouldn't bother with diagonals - they wouldn't be a major contributor to aliasing.
I really wish I could help you more, but all of my experience involved working with a limited number of attributes (SCREEN 12) where you already know the hue of each attribute and create antialiasing values in advance.
To be honest, I'm amazed at the efficiency of certain code in professional Photo/Paint apps. Converting bit depth, resizing images -- it all seems so instantaneous. I, on the other hand, am a self-taught programmer, so most of my code is pretty obvious and time-consuming.