Best results I have had is editing the image with photoshop and using the following settings:
640x480, 16 Bits/channel, and save as a maximum size jpeg with 100% quality. This produces a crisp image on the phone with 0 pixelation but the file size is around 240k.
I found that even bumping the quality down 10% to reduce file size added a small amount pixelation to the image.