Initial Upgrades
These are the upgrades that are fairly easy, and should be done first before anything else:
RAM
This is probably the most important. Take the RAM all the way up to 144mb. You'll appreciate it. My install of Mac OS 9.2.2 takes up about 40mb of RAM with Virtual Memory off. This leaves about 100mb available for programs to run.
Hard Disk
Recommended. I upgraded my machine to a 40gb hard drive. It is an IBM brand drive, which is what Apple usually uses originally. It runs quiet, fast, and is huge!

CD-ROM Drive
I upgraded mine to a 20x model, pulled from a Kanga G3 (the PowerBook G3 that looks like a 3400c).
ZIP Drive
I haven't done this yet, but they are available. These will be great for big backups that don't fit on floppies.