You might want to change your interpolation type when adjusting the image size (drop down box in the Image Size menu) Bicubic or Bicubic Sharper will probably produce the best results. (you'll get straight lines, but they'll be much lighter - you can then darken the image and increase its contrast to make it look more like the original black lines.)

Alternatively you can redraw it in the smaller size with the line tool (it has a checkbox to turn off AA) or the pencil tool which will let you draw one pixel at a time.

I would create this image (the cube in this case) in a vector graphics program such as Inkscape and resize it before converting to or in another program which supports vector to raster conversions like GIMP. Once you get used to the workflow pipeline, using one vector program and another raster program in this way is quick and easy.

For very advanced work, I make a cube or other 3D object in a 3D program and rendered with lighting effects and fine anti-aliasing, perhaps super-sampling, then take a screenshot of it already in the correct size. After getting the experience, both these methods take me about the same amount of time for simple shapes or images.

Clinton