1. Grab an organization chart for your entire organization [Edit: or a functional chart for your organization (org chart will probably break down by department; functional chart would break down more by the roles or maybe the purpose of sets of departments and may be easier for users to understand)]
2. Have the SharePoint admin create site collections for each major division within your company
3. Create SharePoint sites for each major department
4. Create SharePoint sites INSIDE those sites for each sub-department
5. Start at the top and create SharePoint groups for each and every level (create a group per site collection, another per upper sites, and another for each of the subsites)...so every site has its own group. These are your broad team groups and you should place any Active Directory groups for these inside the appropriate SharePoint group. This makes managing the entire team a little easier on the SharePoint end because if someone changes departments or leaves or is a new-hire then they are updated in Active Directory (which updates their sharepoint permissions automagically). [Edit: Note: if you use multiple site collections as I'm implying, you may want to use more Active Directory groups for those that need to reuse groups across site collections. If it's an occasional thing, just create the group on each site collection since groups are specific to the site collection.]
SharePoint Managers group: there ought to be SharePoint managers groups for each level so that those who have to manage SharePoint (and are in a trusted position) can do so...often, you can have SharePoint managers for each major department (sometimes you're lucky enough to have them for subdepartments) but give them full control of everything. There may be instances where they cannot have access to something - that should be stored either outside SharePoint or the list/library setup with custom permissions and (after it's all working) remove the SharePoint Managers group from it. Obviously, these should only be your departments' SharePoint gurus. The owners of SharePoint Managers groups should be a higher-level SharePoint Managers group.
Group Owners: every group has an owner but you can use other groups to own or manage groups (manage being adding and removing people from groups). Depending on your needs, it is generally best to have one "Group Managers" group at each site and subsite level that is in charge of all groups within the site but does NOT have ANY permission to do ANYTHING else but manage the groups. This will require some custom permission levels but it's not too bad to setup and doesn't require code or anything. So, who "manages" the "Group Managers" group? That should be the closest SharePoint Manager group's job unless there is a specific department or systems administrator that is responsible for managing all permissions similar to an Active Directory permissions setup. In my job, there is a department responsible for supporting sharepoint and, thus, we are pushing for that team to manage all of these "group manager" groups AND any "SharePoint manager" groups but then have all the smaller/more specific groups be maintained by those in the "group manager" groups. Yes, I know this is prose for a tongue twister, leave a comment if you want clarification.
Group Membership viewable to everyone? Typically, it is best and easiest to make it so that everyone can view the membership of the group (everyone can see who's in what group). This makes for better accountability as well as easier communication when needing to find someone who resides in a group. This isn't always the case (especially in larger companies and places where special, exclusive groups where only those in the group can know who's in the group.
Directors: Directors are special. Typically, directors and those in higher positions are so busy that they don't have time to learn new technologies like SharePoint, so, typically Directors ought to have the ability to read/view everything within the site/subsite and that's ALL.
Telling Directors they get read only: Yea, go ahead, tell your director he gets read-only rights to the site...I'm waiting, give that a try and see how it goes. Here's the solution: you can create permission levels like Read Only (there's already a Read so no worries there) but you could copy READ and make your own called "Director-level" or "Audit" permissions...just make sure you check all permissions under "Personal Permissions" which allows them to create their own views and webparts as well as "enumerate permissions" to list all the permissions on something so they can contact those who "own" a list or site as necessary. This will satisfy their ability to access all information, generate their own dashboards and reports for the information, and they don't have to have the ability to royally screw up SharePoint by going click-happy.
Directors who know SharePoint: So, what happens when you get a director who happens to know SharePoint or learns it real fast and becomes a decent guru at it? Simple, add him to the Director group AS WELL AS the SharePoint Manager group for that level.
Teams who are cross-department or cross-functional: Simple again, just don't create a million groups for them, create the few that works internally for their department and give the appropriate groups permissions to your department info. That's the beauty of SharePoint groups...once they are created for their team, you can reuse them across the site collection (notice, to create groups that reach across all site collections, then the groups have to be created
If you find any other typical exceptions to these that are worth noting, please let me know and I'll add them to the list. Hopefully, this gets you started on a permissions plan.