I like Tommy and Bob's lists. I'd also like:

konsole or equivalent
- because using xterm is a drag. Its as underfunctional as the XP CLI window.

gcc
make
glibc-devel or equivalent
kernel-source of equivalent
- because I've run into distros that have lacked some or most of these, and none I can think of has ever had all of them by default. Which is pathetic because I always have to install something from source sooner or later.

info
- why do ANY distros not have this?

ntfsprogs
- if a Linux install can detect a windows partition to put it into grub, why can't it also install ntfsprogs? And if I could have my way, ntfsprogs would be r/w-enabled. people are always caveating that r/w ntfs access is so dangerous, but I had it on a couple of earlier version of Mandrake (7.0 and 7.1 maybe) and I never had any trouble with it.

all the dependencies and devel packages for mplayer.

gftp or equivalent comfy graphical ftp client

sudo - seriously, I've had to add this to a distro or two after its default install

firewall enabled by default
- I've also run into distros which install a firewall but have it disabled initially. ???

Later addition:
xkill - it's nice to have it because it can be quicker than mucking around with a terminal, and - there've been at least a couple of times when I couldn't otherwise get rid of an obstreperous misbehaving graphical app without killing xwindows with ctrl-alt-backspace.