While Ubuntu is a clear favorite of mine, there are quite a few programs that are needed before I actually enjoy using it.
Here's the list:
konsole: A better shell
kopete: A nice IM app
emacs: Programmers text editor
gftp: An ok, but not great FTP client. I wish there existed a better alternative
vlc vlc-plugin-* mozilla-plugin-vlc : The video player that plays everything
amarok: A Jukebox application - pretty similar to ITunes.
easytag: ID3 tag editor, with most of the functionality I could wish for.
dia-gnome: A tool for creating diagrams, both UML and others.
rar unrar: packing and unpacking tools
build-essential: gcc, and other tools needed to compile programs
vpnc: a command line VPN client
krdc: My favorite VNC client. Can also be used with other types of remote desktop servers.
ssh: umm, an SSH client?
cvs: CVS client - has mostly been replaced by SVN, but still nice to have.
tetex-base tetex-bin tetex-extra auctex preview-latex: LaTeX with all the trimmings
subversion: SVN, a versioning system.
sun-java6-plugin sun-java6-fonts sun-java6-jdk sun-java5-jdk: JAVA runtime and developer kit
tilda: a Quake style console, doesn't work too well with Beryl, though.
agave : a colorscheme creator. Nice for people like me who has no aestetic sense.
flashplugin-nonfree: What it says it it, a flash plugin for Firefox.
gnome-compiz-manager: additional configuration possibilities for Compiz/Beryl.
network-manager-gnome: A nice Network configuration interface. Still not really good, but better than straight text files.
emacs-extra emacs-goodies-el: lots of extra functionality for Emacs.
Generally, the first thing I do after installing ubuntu is adding all of these.