I currently have an OpenBSD firewall running on an ancient 586. I have a mini-itx board, CF/IDE converter and a CF card and have been intending to upgrade.
However - rather than OpenBSD I'm going to try for debian (since I know that much better).
This post will end up being a "how I did it" - but at the minute is just a collection of the notes I'm grabbing for now.
For the initial install - I hung a CD-ROM as the slave IDE unit on the primary IDE channel.
I used the 4.0r3 etch netinst CD downloaded from debian.org.