600x600 should be fine. Larger is possible as well, however tend to consume a lot of additional disk space too
If you are missing covers, have a look at the following site:
http://www.albumartexchange.com/covers.php
For a Mac program to support you to find covers, you could give Coverscout a try:
http://www.equinux.com/us/products/coverscout/index.html
(I know, not the cheapest around, but which large libraries it can save you a lot of time)