-Turn off Anti-Aliasing for everything (not just fill tool and pencil tool - EVERYTHING).
-Rotate and/or resize (not ImageSize, mind you..) with Transform Controls w/out AAing...
-Paste WITHIN layers (rather than creating a new layer, combining with the next layer, then moving it around... what a chore!).
-Make Line Tool show what it's going to do before it does it in pixels.
-Change pencil tool to be square (I'm sure this one's easy - I just don't know it, though)
-Turn a pixel grid (similar to the zoom in Ctrl+G grid of MSPaint)
(I'm using the CS3 beta, so some of this might not be in your version)
I think the global removal of AA you're looking for is under
"Edit>Preferences>General>Image Interpolation"
I would say probably nearest neighbor is your best bet, It's worked well for me for some other pixel stuff. I haven't tried it but I'm pretty sure that's it.
For the line tool... I'm guessing you're aware that you can hold shift to constrain the line to certain angles, I'm pretty sure there's some way (although I can't remember what it is) that you can edit those angles. Would that help you? Most of the time the line it makes is jagged and not precise enough for pixel art anyways.
If you can't get square brush settings working, you could just make your own... I haven't made any in forever, but I think you can do it by just making a new image with whatever dimensions (square, obviously), filling it with black, and going to Edit>Define Brush Preset. If that doesn't work, you need a selection of some kind.
Pasting without making a new layer should be pretty easy, but I can't find it. I'll ask around and get back to you.
