As @leo.r said, PDF/X-1A will give you the format they want, as far as flattened transparency, but it cannot help your low resolution images (and in all probability there is no way to increase the resolution to make them look any better other than re-scanning an original print).
CMYK color spaces are smaller than RGB which is why it is generally best to leave images as RGB up until the time of printing (PDF/X-1A does that conversion along with the flattening), but once you have made the conversion there is now way to go back to the original RGB -- any colors lost are lost. Further conversion from one CMYK profile to another can result in more losses and color shifts, and conversion to an incorrect profile for the output device, or the removal of profile tagging in the PDF (again a feature of PDF/X-1A) also can cause color shifts. I like to explain CMYK profiles as being like regional language dialects. depending on where you are, the same words identically spelled can be pronounced very differently, and to get the same pronunciation you need to alter the spelling.
Unfortunately you are far down the road of no return here and using a printer who will make no attempt to do color matching, and your best bet probably really is the PDF/X-1A standard. As for which CMYK space is best, you can only guess and my suggestion is to use one of the most commonly used standards in the country where the printing will be done. In the US that would be SWOP, in Europe I believe one of the FOGRA profiles is preferred, but I don't know which one.
... View more