Don't forget the Zaurus, too
Both the iPaq (many models) and Zaurus can accommodate many of the "standard" tools.
For the tiniest option, I would recommend the Zaurus
There are many Linux projects for the various iPaq models.
As for the PSP, I have no idea! I'm sure someone else can comment on that
But it depends on what size device you are really looking for.
There are now many 7" to 9" screen sized devices appearing on the market, like the eeepc.
BT has been designed to run on the eeepc nicely, which should give you a fairly well-rounded "portable kit" out of the box. That is probably the simplest solution, imho, as you don't need to deal with the many eccentricities of running such tools on a handheld.