Compression takes time. If it takes X time to upload and it takes Y time to compress for a Z percentage decrease in size, then your goal is to get Y + X - Z*X < X
. Given the human time necessary to even open up a compression program, Y is likely to be a very large number comparably, and it's highly unlikely that you're going to gain any benefit.
Your best bet is some form of lossy compression. An excellent lossy compression program is a simple picture editor that allows you to crop and resize. If you can cut out the parts of the image you don't want and remove the resolution information that is unnecessary, you might be able to get an appreciable difference in size.
Still, my recommendation is simply to shell out the extra cash for a decent internet connection. Cable or even satellite isn't that much more expensive than dialup these days.