Thank you for the replies.
@knc1: I'll make sure to pay my due
@eshcwartz: Thank you for helping me out, I'm still new around here.
@NiLuJe: I'll try and describe my process and show some examples of what's wrong.
Here's what I did to get the photo ready:
1. Rescale to 3:4 ratio.
2. Use a compositing software to turn the image to greyscale and rescale to 600x800. (also changed file to .png)
3. Open greyscale image in GIMP and change contrast and brightness.
4. Select image -> Mode -> Indexed.
5. In dialog that comes up select "Use-custom palette", and select the palette for kindle. I also deselected "Remove unused colors from colormap".
6. In Dithering select Floyd-Steinberg.
7. Export as .png at maximum compression (since it's a lossless format).
Then I just moved the file to the screensavers folder on my Kindle and rebooted. Here are the results of my work. I uploaded the same photos to the Kindle photo viewer so that I could take a screenshot of what it looks like on the kindle.
Original:
Image violates guidelines for size - MODERATOR]
Original on Kindle:
Image violates guidelines for size - MODERATOR]
Optimized (The one with Indexing and Dithering):
Image violates guidelines for size - MODERATOR]
Optimized on Kindle:
Image violates guidelines for size - MODERATOR]