Nmap is perfectly safe to use. Here's the MD5 hash of the version I downloaded for you to compare;
63F103F19E0CAFEFE3FB7D823B0E935F *nmap-4.20-setup.exe
It was downloaded from here;
http://insecure.org/nmap/download.html. A sniffer capture during the download shows I was downloading from 208.97.160.13. Obviously there may be a few mirrors to download from.
BTW, Symantec Corporate Edition doesn't detect this as malware, and also according to Fyodors site, neither does Trend Micro's PC-cillin.