He's right, unless you reduce the size quite a bit, they won't look good. Your screen is fooling you.
To get a good looking picture once the printer (imagesetter or other printing device) creates the screen, you need to have roughly 150% to 200% of your line screen in dpi.
For example, in a tabloid newspaper the line screen will probably be around 85lpi to 100lpi (ask your printer what the line screen will be). That means if the lpi (lines per inch) are 85 then you'll need pictures that are between 128dpi and 170dpi, and if the lpi is 100 then you'll need pictures that are between 150dpi and 200dpi. Any lower than that and the pictures will look jaggy and blurry.
Note that the dpi in question is the dpi after resizing the image. For example if you have a 150dpi image and you blow it up to twice its size in InDesign then you really now have a 75dpi image (half of 150). If, on the other hand, you shrink it down to half its size in InDesign then you now have a 300dpi image (double 150).
Almost any image editing program (such as Photoshop) will give you the dpi of the image.
Note that you are almost undoubtedly violating copyright if you retrieved the images from the web, taking advantage of someone else's hard work without compensating them at all. You might consider if you would like the same done with your hard work. Clip art and clip photography is so stunningly inexpensive these days, it's a shame to not pay someone for the effort, in my opinion.