Are you saving them as JPEG files? If so, try saving them as TIFFs and see if an uploaded TIFF looks better (it should).

Compression is actually not the term you are looking for - it refers to how much an image get "squeezed" when saved as a JPEG. The more a JPEG compresses, the worse it looks. Save a JPEG image as another JPEG (this is what happens when you upload a JPEG) and you essential compress it twice. This often causes an even worse image quality; that's why I recommend uploading TIFFs.

The only problem is that they are bigger so your connection has to be somewhat fast for it to be manageable.

When you say you "compressed" an image down from 1600 to 400, you are really saving you "resized" the image. And resizing does not necessary mean better image quality. In fact, it often produces worse image quality. You will often have to sharpen up and fix up an image after it has been downsized dramatically.

The main reasons we recommend a size like 500 x 750 is so that a) the image size is more managable over the internet connections, and b) it doesn't get dramatically resized by our image uploading software, which saves images at about that size.

What did you mean "doesn't look right?" Blurry?

When you change the size of your image does your software have a re sample tick box? If it does try de clicking it.