Yes, in this case, it was a couple of things - there were too top level categories (all categories were the top most category, and there were a couple hundred of them), and the logs in the database.
I reorganized the categories to have top level down functionality.
For example, if I had categories called Home, Home Projects, Home Works, Home Items... all of these could be in one single category with Home as the top level and the rest as sub categories.
The second item was the database - there were over 3 mil lines of old download requests. When I cleared that out to only include this years downloads, things started speeding up considerably.
On top of all that, my site was being flooded with download requests. I was able to implement the captcha and that took care of fake download requests.
All three of these things made the downloads go SOOO much faster.
Kudos to Colin for helping me out so much. He found the first issue, and helped me implement the Captcha.