You should take a look at the HTC Touch Pro or similar phones for what you're looking for. You don't mention a particular carrier, but there are both GSM and CDMA versions currently available. If you can hold out a bit, the TP 2 is due out soon - not a major improvement, but some software tweaks. Both meet all of your criteria and have a pretty significant number of tweaks/hacks/alternate ROMS available from various sources.