These are questions you should ask the printing house as they will have their own set of requirements. The is much that happens behind the scene when converting an image from RGB to CMYK, so it's best to have them walk you through their specific requirements.
File > Save As > jpeg. Quality 10 is a good compromise between file size and not too much degradation (there will always be some with jpeg, even at "max", so there's actually little point in going all the way up to 12).
But first of all, if they want CMYK, you need to know which CMYK. This is important! There is no such thing as just "CMYK". Every CMYK profile corresponds to a specific printing process, and you need to know which one. Otherwise you may get color shifts and all kinds of issues like ink smearing and drying problems.
The Photoshop default just happens to be US Web Coated (SWOP) v2, but that may not be the right one. If you're outside the Americas, it will certainly not be the right one.