Well, you're probably going to have to take the hit at some point, so might as well do the redirects sooner rather than later.
Doing a 301 redirect from the (presumably) old urls to the new you will lose some of the link juice (and I come down on the high end of the spectrum and say you lose 10%, others say less).
You'll also take a bit of a ranking hit while Google indexes the new URLs and repositions you. I've seen this take about 3 - 4 weeks, though could be longer. To aid here make sure and submit a new sitemap as soon as you're done.
Also, while you shouldn't pay attention to such things, remember that your toolbar PR is URL specific, so when you change them you will have all PR0 pages. These should come back after the next update, but they are few and far between. The background PR calculations will still be taking place and should steady themselves long before the toolbar is updated.
As for having to change the URLs, is there a possibility of rewriting them in apache? e.g. is the form site/page?parameter=category¶meter=pagename
So ultimately, yes you will take a bit of a knock, but overall it probably needs done and if you build from it then you should be able to recover and improve much more easily.