Server Restarts and Respective Orders

To answer your question directly, the order of reboots does not matter if the servers are configured to use cached credentials and there aren't any errors in the DC's AD log regarding a particular client.

You only have one DC? Get a second DC. Seriously. Promote a file server running on a 486 in the basement if you have to. Stop running with a single DC. Now.

Otherwise, it should be fine to reboot them in any order, as long as things are all up and happily running between rebooting one and the next.

Also, regarding your virtualization queries: Always keep one DC and one DNS server completely physical. That is, unless you're really itching for a headache.

For Exchange, it would absolutely matter. Exchange does NOT like booting without access to a domain controller. It's not just about credentials, Exchange stores most of its configuration in AD and expects it to be available at all times. I wouldn't be surprised ir your Exchange information store would hang on startup if the exchange vm was to boot up before the DC.

As for the question: Windows Server 2012 has this functionality. Windows Server 2008R2 has some options to control "memory priority" which Microsoft says dictates the boot order of machines, but to which extent I'm not sure.

Here's a little video from Aidan Finn describing the Server 2012 functionality: http://www.youtube.com/watch?v=OEGkbXQZn4M

Here is some documentation from Microsoft regarding memory priority in Server 2008R2: http://technet.microsoft.com/en-us/library/cc956120.aspx