1) Surprisingly, Walmart.com has a pretty good selection of cover art at 500x500 (fairly good size). Just search the album, then click on the cover art picture to get bigger version. Others such as Allmusic.com and Amazon.com have smaller cover art sizes. There are many other sites you can search for (not sure if can post them) that have larger sizes..800x800..but it all varies.
2) I personally stick with 500x500 on mine and resize the bigger ones to that size (for display via MusicLobby on big screen TV). But it all depends on what your preference is and what you are using the images for.
3) If you used the "Update Library" function and had the "Clean Cover Directory" option checked then it would have deleted any cover art not linked to a song within MC. You might make sure you uncheck it, especially if you use a common cover art directory for multiple programs (other than MC). It is normally unchecked by default.
MC has lots of features that save time (especially tagging), but you do have to make sure when you first start out that you try doing global things such as renaming, updating, etc. on smaller batches of files until you positive that you got it right and that it is doing what you expect.