Here is the list of packages that I have pared my small RedHat installation down to, along with comments about why I kept each:

at-3.1.8-33                        -- useful job scheduling tool
basesystem-8.0-2                   -- required by RedHat
bash-2.05b-20.1                    -- required shell
bind-9.2.1-16                      -- required to host Todd
bind-utils-9.2.1-16                -- useful DNS tools
binutils-2.13.90.0.18-9            -- compiler tools
bzip2-1.0.2-8                      -- required to extract bzip2 files
bzip2-libs-1.0.2-8                 -- required by bzip2
chkconfig-1.3.8-1                  -- useful start script management tool
coreutils-4.5.3-19                 -- lots of important shell programs
courier-imap-2.1.1-1.9             -- IMAP server
cpio-2.5-3                         -- extract/create cpio files
cpp-3.2.2-5                        -- C pre-processor
cracklib-2.7-21                    -- required by PAM
cracklib-dicts-2.7-21              -- required by PAM
crontabs-1.10-5                    -- required job scheduling
curl-7.9.8-5                       -- required by PHP
cvs-1.11.2-10                      -- CVS client/server
cyrus-sasl-2.1.10-4                -- required by openldap
cyrus-sasl-md5-2.1.10-4            -- required by openldap
db4-4.0.14-20                      -- simple database needed by lots of stuff
dev-3.3.2-5                        -- device files needed by lots of stuff
diffutils-2.8.1-6                  -- useful file diff commands
e2fsprogs-1.32-6                   -- filesystem management programs
elfutils-0.76-3                    -- compiler tools
elfutils-libelf-0.76-3             -- required to run ELF programs
emacs-20.7-41                      -- emacs base package
emacs-nox-20.7-41                  -- emacs no X11
expat-1.95.5-2                     -- required by python, php, apache
file-3.39-9                        -- mildly useful tool for identifying files
filesystem-2.2.1-3                 -- required filesystem layout
findutils-4.1.7-9                  -- useful find utility
fortune-mod-1.0-20                 -- oh so important fortunes
freetype-2.1.3-6                   -- required by php and gd
ftp-0.17-17                        -- mildly useful ftp client
gawk-3.1.1-9                       -- standard unix text utility
gcc-3.2.2-5                        -- C compiler
gcc-c++-3.2.2-5                    -- C++ compiler
gd-1.8.4-11                        -- image drawing required by webalizer, php
gdbm-1.8.0-20                      -- db libs required by lots of stuff
glib-1.2.10-10                     -- required by pam
glib2-2.2.1-1                      -- required by lots of stuff
glibc-2.3.2-27.9                   -- required GNU libc
glibc-common-2.3.2-27.9            -- required GNU libc
glibc-devel-2.3.2-27.9             -- required by gcc
glibc-kernheaders-2.4-8.10         -- required by gcc
gmp-4.1.2-2                        -- required by php and python
gnupg-1.2.1-4                      -- required GNU privacy guard
gpg-pubkey-db42a60e-37ea5438       -- required RedHat public keys
grep-2.5.1-7                       -- useful Unix text search utility
groff-1.18.1-20                    -- required by man
gzip-1.3.3-9                       -- required to extract gzipped files
httpd-2.0.40-21.5                  -- apache web server
indexhtml-9-3                      -- required by lynx
info-4.3-5                         -- info installer/viewer required by lots
initscripts-7.14-1                 -- required system initialization scripts
iproute-2.4.7-7                    -- internet protocol tools
iputils-20020927-2                 -- useful ip tools including ping
jhead-2.0-2                        -- JPEG tool used by gallery
jwhois-3.2.1-1                     -- whois client
krb5-libs-1.2.7-14                 -- kerberos libs required by lots
less-378-7                         -- less is more
libgcc-3.2.2-5                     -- required by gcc
libjpeg-6b-26                      -- JPEG library required by libtiff
libpng-1.2.2-16                    -- PNG library required by several programs
libstdc++-3.2.2-5                  -- required by gcc/g++
libstdc++-devel-3.2.2-5            -- required by gcc/g++
libtermcap-2.0.8-35                -- required by core libraries
libtiff-3.5.7-11                   -- required by netpbm-progs
libtool-libs-1.4.3-5               -- required by gcc/g++
libuser-0.51.7-1                   -- required by passwd
libxml2-2.5.4-1                    -- XML libraries required by php
libxslt-1.0.27-3                   -- XML stylesheet libraries required by php 
logrotate-3.6.8-1                  -- rotate logs
logwatch-4.3.1-2                   -- possibly useful daily log grokking
losetup-2.11y-9                    -- setup loopback devs, required by mkinitrd
lsof-4.63-4                        -- list open files
lvm-1.0.3-12                       -- logical volume progs required by mkinitrd
lynx-2.8.5-11                      -- text web browser
m4-1.4.1-13                        -- GNU macro preprocessor
mailcap-2.1.13-1                   -- mail capabilities required by apache
mailx-8.1.1-28                     -- command line email required by logwatch
make-3.79.1-17                     -- source build tool
MAKEDEV-3.3.2-5                    -- manage dev files, probably needed
man-1.5k-6                         -- read man pages
man-pages-1.53-3                   -- man pages
mingetty-1.01-1                    -- required terminal program
mkinitrd-3.4.42-1                  -- make root disk, required by up2date
mktemp-1.5-18                      -- shell script file naming utility
mod_perl-1.99_07-5                 -- apache PERL module
mod_python-3.0.1-3                 -- apache python module
mod_ssl-2.0.40-21.5                -- apache SSL module
modutils-2.4.22-8                  -- required by initscripts and mkinitrd
mount-2.11y-9                      -- required for mounting filesystems
ncurses-5.3-4                      -- curses lib required by lots of programs
netpbm-9.24-10                     -- required by netpbm-progs
netpbm-progs-9.24-10               -- required by gallery
net-tools-1.60-12                  -- useful networking tools
newt-0.51.4-1                      -- screen drawing lib required by up2date
openldap-2.0.27-8                  -- LDAP required by gnupg
openssh-3.5p1-11                   -- openssh base
openssh-clients-3.5p1-11           -- openssh clients
openssh-server-3.5p1-11            -- openssh server
openssl-0.9.7a-5                   -- openssl libs
pam-0.75-48                        -- pluggable authentication modules
passwd-0.68-3                      -- password management
patch-2.5.4-16                     -- patching source files
pcre-3.9-10                        -- required by grep
perl-5.8.0-88                      -- PERL
perl-CGI-2.81-88                   -- PERL apache CGI stuff
perl-DB_File-1.804-88              -- PERL DB stuff
perl-DBI-1.32-5                    -- PERL DBI stuff
perl-Filter-1.29-3                 -- required by PERL
php-4.2.2-17.2                     -- PHP
php-imap-4.2.2-17.2                -- PHP IMAP, required by squirrelmail
popt-1.8-0.69                      -- arg parsing required by lots
procps-2.0.13-1                    -- very useful process utilities
psmisc-21.2-4                      -- mildly useful process utilities
pspell-0.12.2-16                   -- required by PHP
pyOpenSSL-0.5.1-8                  -- required by rhnlib
python-2.2.2-26                    -- Python
python-optik-1.4-2                 -- required by up2date
pyxf86config-0.3.5-1               -- required by rhpl
qmail-1.03-9                       -- qmail mail server
readline-4.3-5                     -- required by python and ftp
redhat-release-9-3                 -- required by RedHat
rhnlib-1.0-4                       -- required up2date
rhpl-0.93.4-1                      -- required by up2date
rpm-4.2-0.69                       -- RedHat package manager
rpm-build-4.2-0.69                 -- builds RedHat packages
rpm-python-4.2-0.69                -- required by up2date
rsync-2.5.5-4                      -- rsync client/server for backups
sed-4.0.5-1                        -- standard Unix text utility
setup-2.5.25-1                     -- required Unix setup files
shadow-utils-4.0.3-6               -- required for shadow passwords
slang-1.4.5-16                     -- required by newt
slocate-2.6-8                      -- file finding utlities
squirrelmail-1.2.11-1              -- web mail
strace-4.4.95-2                    -- program syscall tracing utility
sysklogd-1.4.1-12                  -- system logging utilities
SysVinit-2.84-13                   -- init program and scripts
tar-1.13.25-11                     -- creats/extracts tar files
tcpdump-3.7.2-1.9.1                -- network monitoring tool
tcp_wrappers-7.6-34                -- required by xinetd and openssh-server
tcsh-6.12-4                        -- required by cvs
telnet-0.17-25                     -- telnet client
termcap-11.0.1-16                  -- required terminal capabilities file
time-1.7-21                        -- utility for timing programs
tmda-0.62-1                        -- anti-spam tool
tmpwatch-2.8.4-5                   -- cleans up /tmp
traceroute-1.4a12-9                -- network route tracing utility
tree-1.2-22                        -- view file tree
unzip-5.50-33                      -- extract zip files
up2date-3.1.23.2-1                 -- keep RedHat packages up to date
util-linux-2.11y-9                 -- lots of important Linux utilites
vixie-cron-3.0.1-74                -- periodic job scheduling
webalizer-2.01_10-11               -- web log analyzer and report generator
wget-1.8.2-9                       -- very useful file fetching utility
which-2.14-5                       -- useful command utility
words-2-21                         -- dictionary words
xinetd-2.3.11-1.9.0                -- internet daemon
zip-2.3-16                         -- creates zip files
zlib-1.1.4-8                       -- library for manipulating zip files

This is 163 packages. It's as small as I could get it without breaking dependencies, and still leaving the stuff that I use even rarely. I think I might have broken a small dependency or two when I removed some packages, but nothing significant.

Note that quite a few packages are kept around only because they are required by rhn_register/up2date. Dumping that stuff would eliminate 10 - 15 more packages.

Note also that I only run the following services on my Linode: apache, qmail, courier imap, gallery, named (temporarily), sshd.

Anyone got their package list down to a smaller set than that?