The main differentiator is that PDA phones have touch screens. Often they're all referred to as smartphones though, so it gets confusing.

The BlackBerry curve is a good choice and it's fairly easy to use. It's very good for music playback and OK at video playback. Another choice in the Windows Mobile PDA phone camp is the AT&T Tilt or XV6800 on Verizon which are top-of-the-line powerful PDA phones.