There are basically two ways (plus one variation) to address this.
Your stills are overly-large, for the Project Preset's Frame Size. You can apply the fixed Effect>Motion>Scale to Scale them to the Frame Size (1920 x 1080), or can check Scale to Default Frame Size (that's the variation). Or, you use a program, like Photoshop, to Scale to 1920 x 1080.
Until CS5, PrPro was not that good at Scaling, so PS was the way to go. Things changed with CS5, but one is still shoving around a bunch of pixels, that will not be needed, and this taxes the computer.
PS - This ARTICLE will give you some background, and tips on doing the Scaling in PS.
Bill Hunt: Thank you for seriously upgrading my knowledge on this subject with your answer and your article. I scaled my stills to 1920x1080 in PS and now it looks perfect ind my PrPro sequence.
Great news, and your computer will thank you for it.
Now, if you ever need to work with very large still images, say you have large panorama, and need every pixel to do a long, slow Pan, AE handles large stills better than PrPro does, and can accept larger stills, than PrPro can. That would be my rec.