I decided that my next firewall would not be a home wifi router thing, even running OpenWRT -- I wanted something that I knew I could upgrade and configure to handle whatever comes down the pipe next.
And I wanted it to be fast.
And I wanted it to be cheap.
After appropriate research, I sadly discarded the idea of getting a Ubiquiti EdgeRouter Lite. It's cheap -- $99 -- and fast -- wirespeed gigabit routing on three ports -- but the OS it runs is almost but not quite a supported release. While based on Debian, it lags a major version behind and there is no community-supported toolchain to build it yourself.
(If that changes, it would be a great option for most people. And if you aren't horrified by these lacks, it might be good for you now.)
edit from the future, mid-2015: Ubiquiti is also violating the GPL. That should concern you, too.
I thought about buying a PCengines micro PC. They're reasonably cheap if you assemble them yourself, and can run a standard Linux. Power draw is pretty low, 5-15W. While searching NewEgg, I discovered that the high-end of that range is available from a motherboard manufacturer as an almost-complete unit: Jetway G-T40E barebone PC for $220. I almost got that. Two ethernet ports and WiFi on the motherboard, in a nice small case.
Turns out that the successor to AMD's T40 is a relatively new chip called the Athlon 5150 or 5350, depending on speed. And NewEgg had a sale bundle: buy a 5350, an MSI AM1I motherboard, and a miniITX case for $118, about $40 off the regular price of all three. The miniITX case had excellent reviews, takes a standard ATX power supply, and even came with a thermally-regulated 120mm fan in front.
So I got that, a 64GB SSD, and a power supply. I had several 2GB RAM sticks lying around, and 4 GB is certainly enough for a firewall. Intel gigabit NICs run $20-30 apiece. All together, I got a modern small-but-not-tiny machine for about $220.
But how fast does it boot? About 3 seconds for BIOS initialization, a 5 second delay for GRUB to see if a human wants to stop the boot, and then 4.3 seconds to a login prompt, an additional 3 seconds for the ethernet to be up and happy. Call it 15 seconds from cold.
Debian Wheezy, 7.7, x86-64 architecture, 4GB RAM, that's a CPU with a maximum TDP of 25W and an idle around 5W.