You can make nearly all images small enough to upload and still look good without dropping colour depth. There are 3 ways to achieve it basically:
Resize it to a lower resolution (1280 x whatever looks just fine on a screen)
Reduce the quality
Change to lossy (JPG) from non-lossy (PNG)
The resizing is usually enough.
The quality reduction is something that google pagespeed focuses on too. For most apps that means choosing a lower "quality" when converting to jpg or saving as a new jpg. 85% of original is good.
If you happen to have imagemagick installed, I have a little script that I use called "resize_to_pagespeed.sh". The jist of it is this:
photos will never be pngs unless someone intentionally converts them to that format, as pngs are much worse than jpgs for storing this type of image. pngs are much better for computer generated images, such as screenshots, drawings, etc. you can also losslessly compress pngs with tools like pngcrush without converting them to jpg.