Speed hints

Booting

If your computer takes a long time to boot, then it's probably because it's loading a slew of unnecessary programs. Many distributions try to simplify things by having everything you might ever want running by default. Needless to say, this is slow and a security risk.

Note: changing your boot sequence could prevent your computer from booting. Make sure you know how to fix it if that happens! (eg, by typing linux single at the LILO prompt and using the shell)

Here are some good ways to find out what useless stuff you've got running:

Things to get rid of

Of course, any of these might be useful in some particular situation. I'm describing this for a typical single-user desktop machine.

NFS
The Network FileSystem lets other Unix machines access files on your computer.
Netfs
You only need this if you want to mount network filesystems (i.e. from other computers) automatically at boot time.
Samba
Like NFS, but for Windows machines. Also allows people on other machines to use your printers.
FTP (wuftp)
A way to provide files to the public (use ssh instead to provide private files).
Sendmail, exim
Email programs send new emails to sendmail, and sendmail sends them out. Sendmail can do clever things, like sending email to another user on the same machine without going via the Internet, or holding mail in a queue until you connect. For a home machine, it's usually better to get your email client to connect directly to your ISP's mailer.
Telnet, rlogin
Highly insecure ways to let other people run programs on your computer (replaced by ssh).
Apache
Lets other people view a web-site hosted on your computer. Probably only useful if you're a web developer.

Things you might want

ssh
A secure way to access your computer from elsewhere. Ssh can also be used to tunnel through a firewall (to access things normally only available from the machine itself) or to copy files.
xfs
Actually, you don't want this, but disabling it might mess up your X server if you're not careful. Remove lines like FontPath "unix/:7100" from your XF86Config file and see if it still works. XFS provides blocky, ugly fonts to old programs on your machine and others. ROX applications and many others use the new font system instead, and the X server can still provide the old fonts itself (make sure you still have a line like FontPath "/usr/lib/X11/fonts/Type1" in your config, or the X server may refuse to start).
portmapper
Used by FAM (I think) to let nautilus and konqueror update their directory displays automatically when something changes. ROX-Filer can do this without needing the portmapper. You can probably remove this. Some other things use it too, like NFS.
wwwoffled, squid
These programs cache web pages to make web access faster. wwwoffled also allows you to revisit pages even if you're offline.

Things to keep

cron
Runs scheduled tasks at certain times. In particular, it runs logrotate to stop your log files from growing without limit. However, you might want to turn off some of the tasks (see /etc/cron.daily, etc).
lpd
The printer spooler. Print jobs get sent here, and then on to the printer. You need this if you want to print.

Fast booting distros/Unixes

There are some Linux distributions and other Unixes which startup fast and run almost no services by default, for instance CRUX (my CRUX needs 20 seconds until login console is up plus 10 seconds for starting XDM), FreeBSD and NetBSD.

Starting services in parallel

Linux tends to do one thing at a time when booting, to make errors more obvious. If you care more about speed, you can run them in parallel. For example, adding an & to the end of a command will let the boot sequence continue while it executes (ifup brings up interfaces, which may involve slow DHCP negotiations):

  ifup -a &

Here's an excellent (technical) article from IBM, showing how the make command can be used to start services in parallel wherever possible:

Why does my computer suddenly thrash the disk for about 10 minutes soon after I turn it on each day?

It's probably slocate indexing all your files for the locate command.
It's supposed to happen around midnight when noone's around, but most people don't leave their machines on all the time. Use System to find where it's being run from (probably something in /etc/cron.daily) and move it to cron.weekly or cron.never, etc.