You're right, standalone PDAs are hard to come by these days. The only ones left are the HP iPAQ models running Windows Mobile. There really isn't something in between a PDA and a smartphone, especially if you're looking for desktop syncing.

Keep in mind that Verizon requires a data plan with smartphones, so your monthly bill will go up, assuming you don't have a data plan with your current phone.

Do you use Windows or a Mac? If you're syncing your Tungsten E2 to Outlook, then you can sync with Windows Mobile smartphones (or the iPAQ line of PDAs I mentioned). You can sync the Palm Pre Plus to Outlook, but it requires separately purchased software. If you weren't using Outlook, there are also sync converters that can move your data from Palm Desktop to Outlook.