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).