I heard good things concerning the Treo, but never tried it. On the other hand with these types of toys it all depends on what your carrier carries, so some of them might not be available here. The only down side (not a big one) with any PDA-phone (including the BB) is that if you are holding it to your ear you cannot see ten screen. So you have three choices
1) either need to have and carry an ear piece with you all the time
2) not use the PDA part while on the phone
3) use the PDA part while on the phone, but make sure you tell the person on the other end that you will be off for a bit (while you are looking at the PDA)

For my Dads birthday I got him a CLEO that had a keyboard and that was bluetooth enabled. I got him that because his PDA broke and he wanted one with a keyboard. He does not have a Bluetooth phone, so I could not try that part of it, but in theory that could be an other solution