I recently did this with our site of a similar size. We had some categorized posts and a lot of date-based posts (like /issues/cwa/archives/2016/02/post-title) and we moved everything to new categories. We changed our domain name as well, which was an additional issue.
We did it all at once. The month we made the change we had about a 15% dip in organic traffic, which slowly grew the following month. By the next month (so starting about 60 days after the change) traffic was up 30% over our pre-change levels.
Now, not quite a year later, we are up 65% over our pre-change levels and still growing (even though there is still more work to be done). So for me, it was well worth it.
My biggest challenge was making sure that I had a careful and comprehensive 301 redirect table to share with the developers—it was a lot of content to categorize. I started with the pages that had the most traffic/conversions and went from there. I still had quite a few pages that were just brought along for the ride (they were outdated and had little traffic), which I just redirected into a general category. I am going through those bit by bit, updating, redirecting, removing as appropriate.
It's a big job, but it can be very rewarding!