G'day
I'm in a fairly similar position, though on a smaller scale. I've just started at a company that's never really had any sort of admin, it's all been fobbed off to 'good friends who know all about computers', as a result, there's no documentation, no policies of any sort, and absolutely no structure.
My induction consisted of "There's your computer and umm there's the server thingy. I'll leave you to it."
I didn't know the server admin password, but it was logged in and I was able to set it without knowing the previous one.
I started with documenting network layout and hardware inventory - this has helped me form in my mind a vague plan for upgrade paths as well. From there, I moved to looking towards a software inventory (only to find a CD rack half full of empty cases, a few disturbingly burned-looking CDs and no licensing information).
I've got a list of all the software installed on the machines, and my next step is to run a survey of the users to try and work out whether the software they're using is the right stuff for the job and if training is required.
My advice is (and I don't know if it's fully applicable to you, Aaron) to be firm on your recommendations. If you come up with some big plan with intricate interdependancies which is the most efficient roadmap to a stable and secure operating environment for the network and its users, don't allow managers to pick the features they like out of it and prioritise them.
My first big fiasco was when I implemented a password policy (passwords were people's first name and EVERYBODY knew everyone else's password - an account monitoring nightmare) which I'd recommended should come after a survey and a standardisation of installed software (so that people aren't using others accounts to access specific software).
My boss wanted Outlook Web Access, and when I said it couldn't be done until we implemented a secure password policy, he said "You can draft that this afternoon and we can put it into effect on Monday."
The plan was to let the department heads do the education part of the policy rollout as I'd just started and a mass mail type situation wasn't personal enough.
Come Monday morning, it turns out that nobody knew their passwords were going to expire, couldn't understand why they had to have letters AND numbers, and believed couldn't get vital jobs done because x was sick and nobody knew their password.
If you're paid to give advice, letting people who have no idea what's involved change what you've recommended isn't doing your job (that's not to say you can't negotiate, but there are some things that you shouldn't bend on - particularly if it means more work for you later).
My first thought was a mental shrug along the lines of "Well, he's the boss," but it meant a full whole lot of firefighting, a week's worth of reduced productivity across the business, and user education that could easily have been avoided.
