I always feel compelled to mention joeyh's moreutils whenever a discussion of coreutils comes up. If there was a sequel to coreutils it would be moreutils.
chronic: runs a command quietly unless it fails
combine: combine the lines in two files using boolean operations
ifdata: get network interface info without parsing ifconfig output
ifne: run a program if the standard input is not empty
isutf8: check if a file or standard input is utf-8
lckdo: execute a program with a lock held
mispipe: pipe two commands, returning the exit status of the first
parallel: run multiple jobs at once
pee: tee standard input to pipes
sponge: soak up standard input and write to a file
ts: timestamp standard input
vidir: edit a directory in your text editor
vipe: insert a text editor into a pipe
zrun: automatically uncompress arguments to command
Since several of these utilities you mentioned have to do with piping, I thought I'd mention a bash trick that a lot of people haven't heard of. You can take (almost) any command that takes a file name to read input from, and substitute that file name with:
<(command_name)
This will run the named command, send its output to a fifo (named pipe), and substitute that fifo's file name in its place. This is useful if you have to feed output from more than one command into a program -- for example, "join" takes two files, only one of them can be standard input. But if you want, you can do something like this: