Allowable file size is 640x480. In a photo program, such as Photoshop, click on 'image' then 'file size' and change it there.
In case it's still too large to be acceptable for the gallery, reopen the pic in your photo program, then click 'save as' (using the same file name). You will get a prompt telling you that the file already exists, and do you want to overwrite it. Click 'okay'. Now, if it's already at 640x480, you need to change the Jpg compression there. Instead of 'large file' at maximum of 12, reduce it by using the slider to a smaller file, till it's no more than 130 Kb.