I bet you will have to jump through a lot of hoops to manifest all the changes--especially if you the objects at hand have Validation Rules and associated Apex Classes and Triggers. But since you have a Full Sandbox at your disposal, which is a literal carbon copy (data and all) of your production, you will have a working modal to see how to implement the changes in a good way.
My first suggestion is to refresh your Full Sandbox before you start rolling out the changes. This way the Sandbox will fully mimic your Production org (except for newly created records).
1-ish
Then, start bringing over your changes from the the Eclipse IDE. If your scenario is even slightly complex, you will probably have to bring over all of your changes in stages. (And remember, every time you try to deploy a set of changes, ALL of your test code must pass.) You'll probably find that you need to make Field changes first, and then you can add your code, but each situation is different.
I've found that the IDE is much better at deploying changes to Object Metadata compared to Change Sets (though the IDE can only create fields, not delete any (easily)).
2
I am nearly sure you can access any Standard or Custom Object via IDE (and API) including User, Profile, etc. Test to be sure.
3
Generally, it is not possible to delete Metadata via the IDE. I've tried to do it before, like trying to delete fields, but it was more complicated than I cared to do.
If you are deploying NEW objects and Apex code, it might be beneficial to create a Package. They are really easy to create, and they bundle all of your objects + fields + code together in a matter of (order of 10) clicks. But if you are modifying current Standard or Custom objects, Packages might be more of a nuisance, and the IDE and Change Sets are probably an easier way.
Changeset deployment usually does not have SLA and what you have experienced is an expected behavior. Deployment time will always vary and how long one deployment takes to complete does not become a benchmark on how long it'll take to complete another
There are times when changeset deployment will hit a legitimate issue such as gack or a lock and when those occur, Salesforce support can definitely investigate and escalate to have the issue rectified. However in few cases the deployment doesn't hit any gack or lock.
If it took this long to complete may possibly be link to the the many post release patches Salesforce.com have been rolling out, as when a patch goes out active requests like changesets are temporary put on hold and resumed when ready, other possible causes of extended deployment time are size/types of component being deploy and how it affect/changes the org, heavy traffic on the instance or simply multiple deployment / validation holding up the total overall deployment process in the org.
However we need to remember there are no SLA with changeset, but if you want to deploy quicker and have more control over their deployment, then IDE / ANT is the way to go.
Best Answer
The order of the elements in a single package.xml are irrelevant. The system intelligently reorders dependencies so that the elements are deployed in the correct order. Occassionally, the system doesn't get it right, though, in which case the order of the package.xml elements will not help you at all. For those situations, you must instead deploy multiple package.xml files and directories independently. Generally, the order within each package will not matter, but packages that refer to elements in other packages will need to be deployed after the elements they refer to.