I currently have a very simple single server exchange 2003 setup.
I'm planning to add a single exchange 2010 server with all roles, and slowly move people over to it.
Technet and several blogs have plenty of guides to setting this up, but none of them seem to mention at which points in the setup there is downtime. Can I install and configure all the exchange 2010 roles on a new server without affecting the 2003 server?
At what point does external email HAVE to start going to the 2010 server instead of the 2003 server?
The only real downtime you will have is when you are moving the mailboxes as Exchange 2003 will force the mailbox being moved to be offline (or if something is not configured correctly when you switch mail flow).
I would suggest that you have your mail flow through the Exchange 2010 HT/CAS before you move your first mailbox there.
The Exchange Deployment Assistant is a pretty good start to get you a basic framework to follow in your migration.
I agree with Rex. From 2003 to 2010, mailboxes move offline. They can take a long time too. I just finished this same process for a client of mine. 71 mailboxes. Information store was around 45Gb. The move of all mailboxes took just over 30 hours.
You will have additional downtime when you "move all replicas" of your public folders if you're using them.