You want to convert the image to a mode that allows anti-aliasing (8 bit gray, 24 bit color etc.). Anti-aliasing is the averaging of pixels so as to make pixelation (aliasing) less apparent. Indexed color doesn't allow this. After you resize the image, you convert it back to indexed color, and most programs will choose the best pallet for you.
So in photoshop, to resize an 8 bit BMP (or .gif or any indexed color format).
Load the image.
Change mode to RGB
Resize the image
Change mode to indexed color and save as 8 bit bmp or whatever it was.