Can you expand more on some of these Android sticks. or provide links? I've been looking for a cheap XBMC solution for a while now.
Sorry for the late reply. Busy, busy, busy...
As Rurouni notes, the Rockchip RK3188 sticks are the most performant around with quad-core Cortex-A9s at good clocks giving quite a lot of grunt for relatively cheap devices.
However, I'm personally more likely to go with a cheaper device and there are plenty of RK3066 sticks around (dual-core A9s).
However, there is a slight issue at present as GPU video acceleration on both of these chips is not natively supported by XBMC so most people who would like to use one of these sticks as a media player may have issues. To get these devices working with XBMC, you need to start playing around with experimental versions of XBMC using libstagefright. Actually, I've just read that the libstagefright stuff has been merged onto the XBMC nightlies so, although in beta, hopefully support will become more stable soon:
http://forum.xbmc.org/showthread.php?tid=168268&pid=1474907#pid1474907
As for the Linux implementation on these sticks, it's named Picuntu and further information can be found here:
http://code.google.com/p/rk3066-linux/
One of the biggest issues with these Android TV sticks is that different devices from the Chinese manufacturers often use different chips here and there (for wifi especially), so you need to make sure you have the correct modules installed to get them working correctly.
If I ever get around to buying such a device, I'm going to have to learn a good bit about Linux, I'd imagine!