I just learned today (via maxm) that GNU Screen can be compiled to
support 256 colors.
So, I got the source .deb and compiled it with
--enable-colors256, and it works.
I fooled around with xterm for a while, and compiled it to use 256 colors as
well. However, while the colors worked, I ran into too many other problems
(meta key not working, screen not redrawing properly, unicode characters not
displayed, can't find a good font, etc.) that I know are all solvable but not
something I really wanted to work on today. So I just stuck with what I've been
using, which is urxvt. That only supports 88 colors, but before I wasn't ever
able to take advantage of even that due to the 16-color limitation of Screen.
The screenshot above is Emacs, showing all 88 colors. Nice improvement. I'll be
satisfied with this for a while, then when I get ambitious, I'll try again to
get 256. I saw a couple messages while searching around that gnome-terminal and
konsole both now have 256-color capability as well (at least in CVS versions).