Does the device require a keyboard? wasn't sure if that was a requirement... are you able to use touchscreen devices?
The Nokia 770
[link] might be an option... or the Nokia N810 which has a tiny keyboard, but it's expensive.. both devices run Linux.
More searching found the "Zipit Wireless Messenger 2", it's very cheap, plenty models are on Ebay for less then $50 CAD, again, runs Linux.
EDIT: Not $50, looks like those Ebay items might not give you an actual unit.. not sure, regardless, they have community portal site..
http://linux.zipitwireless.com/
Review here:
http://www.linuxdevices.com/news/NS5942157201.html