You may want to check out
www.pdaphonehome.com. Theres ton of threads there about the various carriers and pda phone options.
I personally use a Samsung i730 and LOVE it!, but don't know if that phones compatible with your carrier. I have a friend who uses a Cingular 8125 and I know he likes it alot.
BTW, I am NOT affiliated with that site in any way.