I tried going back into Photoshop and downsampling the images.
That is pretty much a useless step. The PDF size is based on your PDF export settings in InDesign. You can place a 200 MB image in InDesign and have InDesign produce a 500 KB PDF file with the right PDF export settings.
There is only so much control one has in reducing file size. Try reducing the number of pages or remove the photos from your layout.