Windows Mobile is made up of 3 different types A) Pocket PC, B) Smartphone, and C) Automotive. Now, I'm pretty sure you don't need the Automotive version.
So you're left with two choices - Windows Mobile Pocket PC, and Windows Mobile Smartphone.
Smartphones are a phone first and data second. So they are meant for one-handed operation, and lack a touch screen.
Pocket PCs are data first and phone second. These are not very good at the one-handed operation. Typically you need to hold the device in one hand and punch away on the screen with the other.
As for Verizon, they currently have the Treo 700w Pocket PC Phone Edition, and they are expected to release the Motorola Q Smartphone shortly. So you can choose whatever device is best for you.
"I have no special talents, I am only passionately curious" - Albert Einstein