Definitely fix the urls. Having worked on a number of large dynamic messes over the past few years, I can say that it usually makes a huge difference in indexability and rank-ability both, especially if you have two or more parameters (=) in your dynamic url strings.
The biggest thing to be concerned with now is adding too many pages at once, as you asked. We just increased total number of pages on one of our sites from around 800 to over 7,000 (added a bunch of stuff to the database) and it went from 1K+ visitors per day from Google to less than 5

. So, proceed with extreme caution. We didn't realize that many new pages were being created, thought it was only a few thousand, but too bad so sad for us I guess... This was a PR6 site with around 3,000 backlinks (mostly from different urls and ips). Tried reverting back to previous state and waiting a month but no change so time to start focusing that site towards ranking better in Y and MSN. I'm still not sure exactly what tripped that freaking filter but it's probably more sandbox BS based on increasing the size of site too quickly (from a % standpoint or numerical basis like X thousands of new pages). Might have been some near duplicate issues at work as well, trying to test some things now. At the time I figured worst case everything else would still rank similarly but we're gonzo, so just be careful. If I have to do it again on another site I'll probably try to figure out a way to automatically add just a handful of new pages per day or something stupid like that to make the big bad G happy...