I have just done this exact thing. The way I did it was to loosen the bed to frame bolts enough to where all we did was take em out when at the shop.
I brought the fenders, tail gate, and bumpers first then dropped off the truck. This saved time from having to do it at the shop. They painted the bed and all fenders etc first then the truck. I would however see if they will do the interior first as it is easier to close off the interior with tape and paper while painting the exterior to avoid overspray. Do it opposite and you run the risk of getting exterior over spray on freshly painted interior. Even though you are not doing the engine compartment, get them to cover the engine and paint the underside of the hood. Good Luck
