I don’t know how I’ve missed these before. A Korean company makes a little handheld “video game” called the GP2X. It runs Linux on a 200MHz ARM processor (it actually has 2 ARM processors, but one isn’t running Linux). From WikiPedia:

• Chipset: Magic Eyes MMSP2 MP2520F System-on-a-Chip
• CPU: 200MHz ARM920T host, 200MHz ARM940T
• NAND Flash ROM: 64 MB
• RAM: SDRAM 64 MB
• Operating System: Linux-based OS
• Storage: SD Card
• Connection to PC: USB 2.0 High Speed
• USB Host: USB 1.1
  
• Power: 2 × AA or via AC adapter
• Display: 320×240 3.5 inch, 260,000 color TFT LCD
  
• TV output
• Physical size: 143.6 mm wide, 82.9 mm high, 27 mm (excl. joystick approx.) / 34 mm deep
• Weight: 161 g (without battery)

The price? Well under $200!

There’s plenty of inexpensive expansion options and you can get an entire development environment for it… there’s plenty of 3rd party applications.