Well, there's the E-TEN Glofiish X500+, which has all the features you mentioned but they don't state whether it supports SDHC for cards over 4 gigs in capacity and we didn't yet have one of those fairly new cards to test it with when we reviewed it. So you might be limited to 2 gigs storage. Here's the review: http://www.mobiletechreview.com/phones/Glofiish-X500-plus.htm
There's also the unlocked HTC TyTN II (the unbranded version of the AT&T HTC Tilt reviewed on our site). It has everything including SDHC support for high capacity cards. The jack is stereo, but it's HTC's proprietary jack and not a 2.5mm. HTC does include a stereo headset with the phone though, and there's an adapter that converts it to a standard jack sold here .
Thanks a lot Lisa, amazing help! It looks like the HTC TyTN II may be the one for me. I'm just going to look into both of the PDA's you suggested and finalise.