Debian/Ubuntu LaTeX Packages

My standard set of packages:

texlive-latex-base  (you need the programs...)
texlive-latex-extra  (subfigure, fullpage, url)
foiltex (foils)
texlive-math-extra (mathptmx)
texlive-latex-recommended (for setspace)
texlive-science (for algorithm2e)
texlive-extra-utils (epstopdf)

( texlive-latex-base texlive-latex-extra foiltex texlive-math-extra texlive-latex-recommended texlive-science texlive-extra-utils )

You could just install texlive-full, but unless you're writing musical scores mixed with Feynman diagrams in at least 13 languages at once, it's probably 650 megs of overkill...

Other packages that look useful:

latex-beamer
latex-xcolor
texlive-bibtex-extra
texlive-font-utils
texlive-fonts-extra
texlive-fonts-recommended
texlive-formats-extra
texlive-generic-extra
texlive-generic-recommended
texlive-latex3
texlive-plain-extra
texlive-pstricks
texlive-publishers

Note that you also need psutils to get a2ps and a few other handy tools.