I'd suggest checking out m0n0wall (http://m0n0.ch/wall). It's a compact firewall distro, with a version that runs on generic PCs. It's got pretty light hardware requirements, runs great on old hardware, and had a pretty good web UI for administration (better than many SOHO/consumer devices from Best Buy, IMHO).
You can find a ton of older hardware on eBay and surplus stores in rackmount form factors (Nokia IP330, Watchguard Firebox, etc) that are basically just Pentium or Pentium II class processors with 2 or 3 NICs that can be reappropriated to run m0n0wall pretty easily and make for great router/firewall/NAT boxes.
The only downside (IMHO) is that it's currently based on an older version of FreeBSD, so it doesn't support some of the newer NICs that are coming built into motherboards these days. But, if you're using it with an older board with a handful of Intel or 3COM PCI 10/100 cards, then it's no big deal.
It also doesn't have great wireless support...basically just Atheros cards for 802.11g, along with a number of old 802.11b devices. Forget about 802.11n (for now), so you'd still need a separate AP if you want to go wireless. Then again, I've found that where most consumer gear sucks is in the routing and that if you turn it into a dumb AP and let another device do the routing and NAT, then you'll be much better off.