My site currently has a menu of the left of the page with links to 6 main sub-sections. I am now considering changing this so the main links are at the top of the site, with sub-section breakdowns in the left menu (so the user is able to better navigate)
However, I have read mixed comments in that menu changes and small design changes can affect SERPS. Is this true, and if so, should I change a few internal pages, see how they fair in Google over the next couple of weeks and then implement changes to the rest of the site?
When it comes to a change to the main site template, I'd just make it for all pages in one shot. It doesn't make a lot of sense to have some pages on one template and others on a very different template.
Gradual changes can make sense when you are changing the url structure, or even moving a large site to a new domain. Ranking drops can happen when you change many titles or meta descriptions at once. But you're not changing URLs or titles or meta descriptions. I've been involved with quite a few changes like this and so far, there have been no ranking problems.