I would recommend an android based phone. It runs linux and you can gain root pretty easily. I picked up a G1 for $100 a week ago used. It can do a lot and was very cheap imo.
Agreed the Droid has a faster processor and more memory etc... but you can only really get it if you use a CDMA provider. If you use GSM phones you will need the Moto Milestone, which is hard to get ahold of.
I wouldn't bother with any phone without an actual keyboard... it will hold one back from doing shell stuff easily.