IDraw is a useful program for making sprites. It has a real-time animation preview, good palette support, and works well with sprite sheets or whatever size.
It was made primarily for use with the RPG Maker series, but should be useful otherwise.
I can confirm that is still works in 64-bit Windows, though it's interface may seem a little too window-based and clunky.