It depends if you need to keep the aspect ratio or not.
but to resize a image personnaly i use a old Paint Shop Pro and i resize it.
To have no interlacing , you have to choose a resolution where vertical is equal or below 288 pixel.
640x488 is good. But the ratio could be strange for your background , it really depends on your image.