It certainly sounds like a compression issue - what makes you sure that it isn't?
There are two factors here - when InDesign makes a PDF, it (a) resamples the images to a specified resolution; and ( applies jpeg compression to the images, unless you deliberately specify differently. And of course, you have varying quality options for the jpeg compression.
Yes, setting up the output parameters is one of the trickiest things with InDesign, there are a lot of options you need to check.
However its worth spending the time to set this up as you can save custom settings and use it repeatedly once you have set up a high quality set of settings.