A few that come to mind, some less known, some more:
- xargs or parallel: run things in parallel, with lots of options
- sed and awk: more well-known but still super useful for processing text files, and faster than Python or Ruby
- m4: simple macro processor
- screen: powerful terminal multiplexing and session persistence
- yes: print a string a lot
- cal: nice calendar
- env: run a command (useful in scripts)
- look: find English words (or lines in a file) beginning with a string
- cut and paste and join: data manipulation
- fmt: format text paragraphs
- pr: format text into pages/columns
- fold: wrap lines of text
- column: format text into columns or tables
- expand and unexpand: convert between tabs and spaces
- nl: add line numbers
- seq: print numbers
- bc: calculator
- factor: factor integers
- nc: network debugging and data transfer
- dd: moving data between files or devices
- file: identify type of a file
- stat: file info
- tac: print files in reverse
- shuf: random selection of lines from a file
- comm: compare sorted files line by line
- hd and bvi: dump or edit binary files
- strings: extract text from binary files
- tr: character translation or manipulation
- iconv or uconv: conversion for text encodings
- split and csplit: splitting files
- 7z: high-ratio file compression
- ldd: dynamic library info
- nm: symbols from object files
- ab: benchrmarking web servers
- strace: system call debugging
- mtr: better traceroute for network debugging
- cssh: visual concurrent shell
- wireshark and tshark: packet capture and network debugging
- host and dig: DNS lookups
- lsof: process file descriptor and socket info
- dstat: useful system stats
- iostat: CPU and disk usage stats
- htop: improved version of top
- last: login history
- w: who's logged on
- id: user/group identity info
- sar: historic system stats
- iftop or nethogs: network utilization by socket or process
- ss: socket statistics
- dmesg: boot and system error messages
- (Linux) hdparm: SATA/ATA disk manipulation/performance
- (Linux) lsb_release: Linux distribution info
- (Linux) lshw: hardware information
- fortune, ddate, and sl: um, well, it depends on whether you consider steam locomotives and Zippy quotations "useful"
