Hi,
I would do it all at once, nothing unusual about it and google may not see the change on all pages at the same time anyway.
For the rankings it is really impossible to say, you might get lucky, you might have to be patient, its not exactly like starting over again, especially if you have a couple of existing external links but....
For the canonical tags, there is a way to do it depending on your setup. Have you got canonicals being automatically added to the category pages as well as the product pages? If yes then you can overwrite them on a case by case basis by putting the following code in the 'custom layout update' box (this works for both products and categories actually).
<reference name="head"><action method="removeItem"><type>link_rel</type>
<name>http://www.domain.com/oldurl</name></action></reference>
<action method="addLinkRel"><rel>canonical</rel>
<href>http://www.domain.com/new-url</href></action>
You will need to identify the canonical url being inputted into the code, add it to the oldurl bit above to remove it and then put in the new canonical url you want. Needless to say, it pays to be sure about what you are trying to achieve and why before implementing this setup on a lot of pages.
Hope it helps!