Does anyone know how to dither a 24-bit bitmap to 8-bit really fast? (I''m talking one full-screen dither per frame!)

Dithering by error-diffusion is reasonably quick. Check out "Computer Graphics, Principles and Practice" by Foley, van Dam, et al.