Doing everything at once gets it over with in one go, but at the risk that it won't go very well.
I would changing one element at a time. Toddlers are a bit like people with autism; they like fixed patterns and repetition, any change can be upsetting. Especially when you're facing big changes, tread lightly.
I can't really say "do one change every two months" because every change is different and will take a different period of time to adjust to, respectively to learn. But here' my totally subjective gut feeling:
- adjusting to new home: four weeks.
- adjusting to new daycare: six weeks.
- adjusting to new bed: four weeks.
- potty training: a year?
More importantly than the spacing is that you really focus on the change:
- Prepare positively, talk about it in advance, make her understand that a change is coming up and make her look forward to it. Address any concerns or fears. Talk about it a lot.
- When the change comes around, find reasons to give sincere praise on specific details.
Update: How far in advance?
You can start talking about it as you as you actually start planning it; simply make it a topic that is talked about in the family. Start specifically preparing your child only a few weeks in advance, maybe 2-3 weeks.