500x500 is OK if it is the best I can find. I prefer 600x600. There is usually not a need to go larger unless the cover is especially detailed or has small text. But more than the size is the quality. A good clean scan with touchup editing and the colors corrected. The quality of the cover art at
Album Art Exchange is the kind of quality I'm after.
The 600x600 art at iTunes can be OK but can also be rather poor with compression artifacts, poor color, or just a bad scan or source to begin with. Amazon has 500x500 covers but suffer from too much jpeg compression artifacts. Buy.com has 500x500 covers and are generally better quality than Amazon. Other online sources are hit or miss.
If I can't find what I want online I'll scan the cover myself. That's a last resort though because it takes so much time. If I find a reasonable online image but it needs some cleanup and editing I'll do the necessary editing if I have the skills to do so (I'm no image editing guru).