What's the simplest Linux capable board I could make at home?
I'd like to see this too, but my gut instinct is to say "maybe, but it's a lot of work".  Even the smallest Linux distro is going to need around a megabyte of RAM to run.  This means at least 30 or so additional pins for the RAM controller in the microcontroller, and a couple of big RAM chips.

One of the simplest architectures I know that has Linux for it is the Atmel AVR32 series of parts.  The smallest, the AT32UC3A0128 comes in a relatively hacker-friendly 100-pin TQFP package.  This is at least amenable to hand-soldering, unlike most of the OS-capable embedded microcontrollers that come in BGA packages. (the chips that have the little solder balls underneath them)  You can get an idea as to the complexity of a circuit using that chip by examining the EVK1100 eval board.