Here's a few of my favourites.

agrep - approximate grep based on edit distance).

GNU Global - source tagging system that integrates with the shell (less -tfunc displays the function given in the shell).

xmllint - xml validator, pretty printer and schema validator.