Manni, congratulations on your new job! I also started a new job (three months ago) and if I had *that* experience to do all over again (haha), I would say:
Look for the teams or individuals who have been eagerly waiting for a solution and focus on them first, rather than going too broad and bringing along everyone, including the naysayers. In other words, start small with the champions and advocates. Their success will be great selling tools to show the other teams, and their energy will hopefully be contagious.