Unix without a GUI for old machine
You can afford to run a GUI without problems, but I would advise against the more recent "desktop environments". For a 133Mhz machine, I also advise against a standard installation of any recent "consumer friendly" distribution, as they tend to have a lot of background services running.
Installing Debian, ArchLinux, Gentoo, BSD should be no problem. Get a "minimal" installation running first, add programs as needed and check out sleek alternatives, in particular for graphical applications. Then XFCE may be a nice GUI for beginners. You can get a more old-style Unix GUI feeling by installing window managers like openstep, afterstep or fvwm2. These don't integrate the "usual desktop tools" like a control panel, they are only frameworks for working with graphical applications, like a browser or pdf reader.
When installing graphical applications, you have to consider that the apps of the KDE or Gnome projects tend to be a bit heavy-weight. For example, the Okular pdf reader is very nice and has IMO the most decent feature set, but it will require you to install several KDE services and libraries, and will start several of these services in background. For your system you should try some smaller alternatives like epdfview or the more old-style xpdf.
The same goes for browsers, mail, chat, etc. There are some very good console-based apps that are even lower on resources, like mutt, slrn, vim/emacs, mpd, links2 etc. But even on your system I would use them from within X, for more convenient multi-tasking.
If you aim for the old-style Linux installation feeling, the BSD installers were surprisingly braindead and primitive the last time I tried (some years ago). Debian is also text-based (but more intelligent), and when selecting a "Minimal" installation it will also just install the most basic things to boot you into a Linux shell, with the option to select and install whatever other programs you need. I still take this approach when installing new servers or desktops, since the standard installations typically install all kinds of junk and are a lot of work for me to clean up again.
PS: In another life I spend a lot of time configuring those extremely flexible old-style Linux/Unix programs, esp. window managers: http://xwinman.org/
No GUI, old machine? NetBSD would be my choice (though the installation is a pain if you're not used to setting everything up yourself). On second thought, FreeBSD 9.0 is much easier to set up and support will be easier to find. It doesn't use too much memory and your arch is probably supported.
Try Arch Linux. I normally hesitate to recommend it to beginners, but it certainly fits your requirements and can be made quite small with only the basic packages.