I just spent 4 weeks updating an entire site with over 1000 pages. It was a redesign to satisfy a couple changes necessary for each page:

1) Moving from a fluid design to fixed width - the site looked different in FF 1.5, FF2, IE6, and IE7, so I gave up and wanted to force a fixed width.

2) My color scheme was too dark and I wanted to lighten everything.

3) I wanted a different presentation of content in places.

4) I wanted to move ads boxes to different spots on the page.

This left every page up for a re-design, but I wanted to do it gradually and not affect the old pages until they were updated.

What I settled on was creating a new css file and new include files. Unmodified pages would still look ok calling the old css file and include files. Updated pages called the new css file (changing background colors, moving positioning, and other factors), new include files for changed header, AdSense code, etc, and many pages needed their content updated.

I started with the main pages of the site, then with the most popular sub pages, and then eventually all of them. I started before Christmas and finished on Monday. The site looks much better, ad revenue is up, and all the content is up to date.

I've done it both ways. The important thing is to make sure you don't eliminate old pages - if you change widget.html to keyword-rich-widget.html, make sure you leave widget.html on the server with a link to keyword-rich-widget.html.

Presentationally (sorry if that's not even a word) you want to make sure your site still retains the main identifying features - that is, you still want returning visitors to know it's still YOU. Logos, etc, should remain in the same approximate location. I've had visitors initially go ballistic because they land on the page and it's a new world.