So I did some looking at the available choices for Verizon and I think you should go check out a Treo 755p. Most recently I've been a Windows Mobile fan, buying bigger and more complex devices each time I upgrade. But back before this whole smartphone nonsense I went through a progression of 4 different Palm OS devices, and was no fan of the Windows PDAs. So if you just want a phone that also happens to have a good, relatively easy-to-comprehend PDA functionality, Palm OS is probably your best move. Short of say, going old-skool and toting around a regular phone and a separate PDA.