Thank you everyone for your replies! 
It's been great having an operational type discussion.
Here is my summary of the thread:
Software:
Linux:
Vyatta
IPCop
Astaro
BSD:
pfSense
m0n0wall (I didn't know this was the base for pfSense until I started researching it today)
Appliances:
Juniper. I have taken a Juniper course and have the Oreilly book, but I'm a Cisco guy pretty much through and through.
Cisco 871 (I see these pop up on craigslist a fair amount. I suppose I'll pick one up and add it to my lab)
Fritz!box (not available in the US) 
<< I would love to get my hands on one of these.
Hardware:
Alix/Gumstix/Sokeris
Various full desktop systems
I got some great hardware sizing advice offline which referenced http://www.pfsense.org/index.php?option=com_content&task=view&id=52&Itemid=49
My choice:
pfSense on a Dell Optiplex (dual core, 1 gig of ram). I think this should be more then sufficient for performing WAN duties and routing on a stick for my 3548 switch. I currently have an 1841 performing those duties and really like it. However I need it for my cisco cert studies.
I was originally going to deploy pfSense in a KVM VM, but it appears BSD paravirtualization support may not be up to the level that Linux is at. If anyone has experience with this, please let me know. I have everything else deployed in virtual machines, but after reading a bit it seems that pfSense in a VM would consume a lot of CPU resources even doing moderate amounts of traffic (10 mbps). I don't want to starve out my other virtual machines.