I've been using Linux as my main OS for well over a decade now. I can hardly believe I didn't pick up on this tip before.
On your linux desktop, open up your favorite terminal emulator. Enter this command:
What number do you see? 8?
8 stinking colors. That's what my terminal is capable of displaying. It's 2009 folks, and my terminal can only display 8 stinking colors.
Load up emacs in the terminal (emacs -nw) and see for yourselves, M-x list-colors-display shows you all of the different colors your terminal can display.
Ok, so how to improve this? On ubuntu:
sudo apt-get install ncurses-term
and stick the following in your ~/.bashrc and/or ~/.bash_profile: