Personally I find JPGs to be perfectly fine for use across Magento unless you need transparency, then 24bit PNG would be the way to go. Keep in mind PHP will compress the file when it dynamically renders the image, so you should supply the highest quality JPG you can (set quality to maximum when exporting from Photoshop or similar).
If you are exporting from Photoshop, make sure you choose "Save as for web", as this will produce much smaller file sizes for the same quality image as it strips out EXIF data and optimises the image for web. See here for more information.
File sizes will completely depend on the dimensions of your images. There's no maximum allowed filesize but your server will need to process the image to generate resized version so don't use huge files. What you have mentioned in your question is fine.
Mage_Catalog_Helper_Image) will automatically resize your images to the correct dimensions as specified in your template files. You should upload images with dimensions greater than or equal to the largest instance of it on your site. For example, if you have a main product image that can be displayed in a zoom panel that requires it to be 1500x1500 then you will need to supply an image at least 1500x1500. If the same image is used for the category page at 200x200 then PHP will resize it appropriately.
You can control the quality of the rendered image by adjusting your PHTML files:
There are also additional PHP libraries other than the default gd2 that you can use that would provide higher quality rendering of images.
ImageMagick seems to be a popular one for better down scaling and avoiding artefacts like moiring