Very early in your tenure, find out what their pain points and annoyances are and either make them go away or help them understand why you can't. Sometimes it's really simple things, like not having access to the best/closest printers, or BS excess process. Once they see you as someone they can go to with their problems, you are the boss.