The AVR32 based NGW100 is about $AUD85 , has ethernet, runs linux, is small, but only has gadget USB. No host USB. This is apparently a hardware limitation. Dammit.

http://beagleboard.org looks interesting, but it's early days