I would also recommend getting images no smaller than how they are going to be on the cover. If you find yourself having to stretch an image very much, it isn't going to look that good. Sometimes one can't find the hi-res image he needs, but sometimes compromise is best.
Great job on what you did in paint, that is very impressive.