You made a good point - what's it doing in /usr/bin? But on my box, that's where nmap lives.

I believe the answer is that nmap isn't root-only. It can be run by ordinary mortals, although some functionality is unavailable to them.