First things first:
aptitude so dependencies automatically get installed and uninstalled. Edit the configuration to not install recommended packages by default. Keep it lean!
openntpd (or some other ntpd) so the computer will know what time it is.
sudo so that I can log in as a regular user and still do system maintenance.
openssh-server (or some other SSH server) so I can log in remotely. I usually change the port number. Make sure root logins are disabled.
tmux so that I can have multiple shells in a single ssh session. screen works for this, too, but I recently switched to tmux.
rsync so that I can copy files around efficiently.
After that, it depends on what I want to do with the system. Usually, there will be at least some software development, so build-essential (libc-dev, gcc, make), irb, git. Usually ssh and some network debugging tools like ping and traceroute6.
I like zsh, so if I'm going to be using the system extensively, I'll install that. If this is my primary system, irssi and mutt. If the system has enough memory to run it, emacs24-nox.
If I want a GUI, xserver-xorg, xterm, whatever window manager I happen to like at the moment (wmii), some web browser (iceweasel).
It's been a while since I've last done this, so I may have missed some things, but this seems to be about it. The package names are for Debian-like systems and will likely be a bit different for other systems, but I don't generally maintain those.