Photoshop is probably better than Paint.NET for sprite animation and game art in general. It’s also a software you should learn if you plan to get serious with game design / art / development. But it’s not really geared toward pixel art, so when you start getting more into it you’ll start wanting some more specific features.
Check these out:
GrafX2 - http://code.google.com/p/grafx2/
ASEPRITE - http://www.aseprite.org/
Tile Studio - http://tilestudio.sourceforge.net/ (Windows only)
Graphics Gale - http://www.humanbalance.net/gale/us/ (Windows only)
Pixen - http://pixenapp.com/ (Mac only)
Making impressive pixel art is very challenging, and animating it is even more difficult. An alternative to having to draw each frame is to break your characters into parts (legs, head, arms, torso) and animate those parts using a software like Flash, After Effects, or even 3D software like Maya or Blender.
Another alternative is to use a 3D program to animate your characters, and then render them to 2D. I disagree with StumpyStrust – just because you’re using 3D to model/animate doesn’t mean your game may as well be 2D. There are lots of 2D games that use this technique (Starcraft for example).