I just ordered a couple PIC16F721 and PIC16F88.
So far I think this pretty well covers the suitableprocessorsfrom Atmel and Microchip. The Microchip processors have the obvious advantage of being through-hole/socketed, but their toolchains are a bit weaker, they're not as powerful, and there's a smaller dev community available.
ThePIC16F721 has 7k of self-writable memory, UART and SPI/I2C, and can run off it's internal 16mhzoscillator. At around $0.75-$1 it would be pretty good for a dual processor design and I'll probably start working with this one first.
The Atmel processors I picked out are kind of oddball chips and don't have that great of support. I've since learned they won't program with the adapter I usually use and I'll have to dig out my old official dev kit to work with them, which could take awhile to find.
So it looks like the 20-pinPIC16F721 is the current front runner. 7k of memory is still pretty darn small by today's standards, but I'll see what I can do with it.