Pygame is usually (and recommended to) run without hardware acceleration. That means that it is slow and to make it workable, you should restrict all unnecessary drawing (blitting etc.) and updating of the screen.
The cost of these procedures (at least of drawing and updating, I haven't actually tried blitting) is directly proportional to the amount of pixels that you are manipulating. Draw only what you need to draw (or blit) and update only those parts of the screen, not the whole screen. (Keep a list of "dirty" rectangles, i.e. rectangles where you have made changes in the last frame, and give that list to the update() call as an argument. IIRC.)