After some discussion with Brian and lots of reading, I've learned quite a bit more about BGAs and ball pitch. I'm now leaning towards wanting at least 1mm ball pitch on any BGA parts used on the TuxedoBoard. 0.8mm ball pitch seems like the dividing line between being able to do a "traditional" dog bone fanout and needing to use via-in-pad. I want to avoid doing via-in-pad if at all possible. Not all board manufacturing houses can build PCBs this way, and even those that can will charge more or have lower yield than other methods. Even Screaming Circuits would prefer to not deal with via-in-pad, although it sounds like they can. I believe they built the BeagleBoards but even they consider the technology used on a low cost BeagleBoard to be special.
With 1mm ball pitch BGAs, two or three 4mil (or 3.5mil) traces can fit between vias, depending on a whole slew of other parameters. Brian warned me that some board houses can't reliably do 3mil and smaller traces, that's good to know. For the number of pins I'm considering for the ARM SoC (in the 300 pin range), a 6 layer board should be doable with 4 routing layers and 2 power. Now, whether 4 routing layers and 2 power is possible for the pinout, that's another question. :)
With this in mind, a minimum of 1mm ball pitch seems the best way forward for now. I want the design to be easy and inexpensive to manufacture at a large number of places. In order to achieve this, microvias and via-in-pad aren't the way to go.
Now, to pin down which SoC will be used!
The Freescale i.MX25 parts are 0.8mm and smaller ball pitch. :( But TI does make the AM1707 ARM9 part with 1mm ball pitch which now looks interesting...