Similar to Steven at my previous Company which had a full adoption. I started going department by department, setting up a Team for the department, and bigger departments I would setup a Team, with channels for the Sub Departments, then I would have sub teams as well. This way the larger department could cross collaborate via the channels, and the sub departments themselves could stay in their silo's of work.
Once I got everyone trained and in Teams, well sometime during the deployment, project Teams started to organically be requested, so I would create these for cross department projects / functions.
After everyone was in Teams, we started a team for company goals and initiatives that the entire company was involved with, with channels per Initiative so the organization could get updates / subscribe to the channels and ask questions. Each Initiative also had it's own working Team that was private the to project itself.
Was working quite well, but now I am at another company where I will be deploying Teams here as well and expect to take a similar approach to deployment.