On the other hand, I have a quad core A9 based appliance that was really cheap and it flies.
The RockChip RK3188 CPU's (don't know if its the one you have but RK3188 is a Cortex A9 based design) are looking very promising in that respect - Rockchip have been unusually open (for ARM SOC manufacturers) in releasing whatever info they can about it (which unfortunately excludes the GPU, as it's an ARM Mali 400, and ARM does not allow manufacturers to release stuff openly), and there's a full Linux distro available for it (Pi%&$#?@!%&$#?@!%&$#?@!%&$#?@!u - Ubuntu derivative, as the name indicates).
No HW accelerated graphics for it yet, and that'll likely remain a challenge. (On the Linux side there's the "workaround" of eventually using the Android display subsystem with Wayland or Mir) But it's still fast enough to be able to do unaccelerated software decoding of 720p video just fine.