When hardening a LINUX system what command line tools would you remove first in order to make an attackers life really difficult?
Most of the native tools are necessary for system administration. There are very few that you could remove without being concerned that you'll need them one day.
You run a serious risk of extending outages or delaying projects when administrators are missing essential tools.
Instead, you should focus on:
Making it difficult for an attacker to communicate with the system (network boundaries, packet inspection, removal of unnecessary services)
Isolating hosts based on sensitivity of data (DMZs, network ACLs)
Blocking inappropriate communication (HIPS, network IDS/IPS, local firewall/iptables)
Preventing exploitation and limiting escalation (patching, app-specific hardening, least privilege users, chmod jails, sandboxing)
The first thing I would do, is to keep off any insecure Telnet/FTP/Rlogin/RSH or other analogous superannuated services.
There are various commands and files that can be captured from people when they are connected on the same network. The solvent of the problem would be the usage of services that implement protocols with SSL/TLS encryption (FTPS, OpenSSH, and others).
Example on a Debian/Ubuntu system:
~ $ sudo apt-get --purge remove nis yp-tools xinetd atftpd tftpd tftpd-hpa telnetd rsh-server rsh-redone-server