If you do software surface blitting you can speed up the alpha blending a lot by using RLE encoding of the transparent surface. I suppose there is special code in there for the case of completely transparent or completely opaque pixels. You can use it with by doing something like surface.set_alpha(0, pygame.RLEACCEL), but I must admit I have only used this with the C SDL functions, so perhaps someone can fill in the details. The '0' is ignored when the the surface has per pixel alpha.
Transparent edges of sprites really look much much better than hard edges, compare for example http://offload2.icculus.org/airstrike/screenshots/ohmygod.png (no alpha) with http://offload2.icculus.org/airstrike/screenshots/screenshot5.png (per pixel alpha) You can generate the soft edges by asking your artist to draw the sprites in high resolution, on a transparent background, and then scale them down. Regards, Ulf