Some thoughts. Warning: you are going to get a headache when you realize all that needs audited...take a deep breath and attack this systematically and logically...

1. Split up what you are trying to audit (targets) first:
* Servers, desktops, network gear

2. Then split up what you are auditing for:
* Network login passwords: LC4 by @Stake, Crack, etc
* O/S vulnerabilities: Nesus (freeware, *Nix platform), Retina is very good (as stated by Soda) but is very expensive, GFI LANGuard isn't bad
* O/S patch levels: M$ MBSA
* Trojans: port scan machines, trojan scanners such as The Cleaner and TDS3
* Web/FTP servers not allowed on network: port scan all devices for 80,21,etc
* Permissions: group memberships, file share permissions
* Open file shares: Shed, Enum, etc
* Internet web sites

3. Prioritize items based on your company's business priorities and anticipated exposures. For example if you run e-commerce on Internet exposed web servers you should focus on these targets FIRST.

4. Perform audit(s)

5. Evaluate results

6. Remediate issues/problems found

7. Re-audit

8. Repeat 4-7 for each area

NOTE: Be CAREFULL!!! You can DOS and even crash systems by simply running a vulnerability audit against them.

I noticed you mentioned about NMap bringing down your Internet connection - this could be caused by any number of reasons: Nmap creating more TCP connections for your client than is allowed, bandwidth causing DOS, etc. Try setting Nmap to a slower speed or fewer threads and try again. You may be filling up firewall connection pool - what kind of firewall/router you running? Do you have egress filtering turned on your firewall/router (re.; ports allowed outbound)? If not you should blocking ports such as M$ chatter (135,137,139,445,etc) and STMP from clients other than approved mail servers.....etc list goes on.

Hope these thoughts help you. Have fun.

<edit>
Forgot to ask: do you have explicit approval from your supervisor/boss to perform this work? You must also ensure you have approval from the people who own or manage the machines you are auditing! Get all of this in writing (email, paper, etc). VERY IMPORTANT!
</edit>