1. Your job is to get the place in shape. If there is unfairness, waste, idiocy, lack of organization, what you want to do is to get the place in shape. People who have special privileges need to realize the party is over, those who are sloths need to realize it's time to wake up. If people have stopped doing research, you want to get them back on track — provide incentives, positive and even punitive.
2. You do not count. No special favors for your friends, your partner's friends, your friends' friends, people who work in your field, etc. If there are fishy procedures or processes, straighten them out. It's all about making the place good enough that you can leave for the next job. If you just want to stay in place, say until you retire, you should resign -- see #5 below.
3. There are bound to be loads of points of friction: those who benefit from the past ("rentseekers" is what the economists call them), those who have special privileges or who are getting away with not doing their jobs, etc. You are cleaning house. While you are doing so, don't leave behind garbage for your successor. Your claim is that you are trying for fairness and comity among your faculty.
4. Don't get in battles with anyone, at least battles that look like battles. You want to have things just happen. If the higher-ups won't help, AND they are stopping you, they need to realize that your job is to clean up the place. If they won't go along, start looking for another position, or just go back to being a professor. Don't be an instrument of someone else's corruption or revenge -- even your most reliable colleagues will use you to do their dirty work. Surely there will be resistance, but again you are acting for a superordinate goal: fairness and excellence and comity. Your righteous resisters need to realize the consequences of their resistance, since they are not only taking on you but also the provost and perhaps the president. If they threaten to leave, make sure you throw them a nice good-bye party and wish them well.
5. You don't need this job. You almost surely have a tenured professorship. If you can't make a difference, get a research grant and go to work.
6. Don't antagonize your strongest faculty. They should be your allies, but if not, you don't want them as your opponents. Of course, a la #1 and 4 above, you will need to ensure fairness, and that may mean problems, but credit that to the provost, the president, and the board who hired you and are forcing your hand.
7. Every few years, ask yourself, What's the next challenge? Keep in mind that you need to resign when you don't see a path forward.
8. It is quite unlikely that you are as strong as a scholar as your strongest faculty. Just because you are dean or provost does not mean people should respect you as a scholar.
9. You are in the sales business, promoting your units or university. Keep that in mind. But don't be deluded by your own patter.