I noticed that PHP3 is available for download as a package from Cobalt's FTP site. However, I was not able to find the newer PHP4. Am I missing something? I'm sure Cobalt would have made PHP4 available for the RaQ 3 by now?

There is no PHP4 Cobalt Package for the RaQ3.

But just follow the instructions on http://list.cobalt.com/pipermail/cobalt-users/2001-February/033275.html
(worked fine for me)

Thanks. And if I want to install MySQL as well, I must do that before installing PHP4 right?

You should first install MySQL and then compile PHP with MySQL. If you want to use PHPMyAdmin later (which is really great -> http://www.phpwizard.net/projects/phpMyAdmin/) you also should compile it with magic quotes enabled.
But you don't have to install MySQL like they did in the tutorial. Just get the latest Cobalt Package at http://pkg.nl.cobalt.com/ and install it first.