PDF is chocking Acrobat on PC

[Dogil]

I made a A5 book with 100 pages and 3 images on each page.
The file is about 500 MB with thumbnails, max 300dpi and automatic compression, CMYK color.
It's a bit heavy, but still opens and scrolls fine on my computer. Linux, 64bit i7 8GB RAM.
However, I go to the printshop and Acrobat there chockes so much on it that the priter refuses to print it and says there is something wrong with my PDF.
What can I do?

[Dogil]

Meanwhile i tried different things to make the file manageable on windows, but nothing seems to help. RGB/CMYK color, less dpi, more compression, less compression, with thunbnails, without thumbnails, no avail.

The images are mostly just a little bit cropped, but about a quarter of them has a slight rotation. I think it must be either of these reasons why Acrobat can't handle the file.