I agree with Lorro. If the original size of the images are small, chances are they’ll get pixeliated when expanded (or stretched) to fit the space.
These are my thoughts, you can use two sizes of high quality images (small and bigger versions). Use the smaller one on the catalog page (thumbnail) and the bigger one for the specific product page. I hope I make sense.
PS.
Are the original images sharp? or Have you tried editing/enhancing the images?