I've chosen an ARM SoC (system on chip) for the TuxedoBoard! The Texas Instruments AM1707 ARM9 core will meet my requirements.
The AM1707 is a 456-MHz ARM926EJ-S SoC that has an internal Ethernet MAC, multiple UARTs (serial ports), an external memory interface for a 32 bit wide SDRAM bus supporting up to 256MB RAM, an external NOR flash memory interface multiplexed with an SD card controller, USB, an LCD interface, and a few other interesting features.
In keeping with the stated goals for the TuxedoBoard project, the schematic capture and layout will be done with Kicad. Kicad supports both Windows and Linux and is covered by the GPLv2 license. I'm currently using the 20100314 release as that's what comes with Debian 6.
I'm in the process of creating the schematic symbols for the AM1707. I'm new to Kicad and I was not able to find an already made symbol with a permissive license, so this is taking a little time. I've made the power symbol and the EMIF_A (external NOR flash / SD card interface) symbol. Some pretty pictures of what I've got so far: