If you are looking for a smartphone, my main advice to you is to go into a store and play around with them. Everyone's "feel" for technology is different, so you may like something that someone on this forum would not recommend. And yes, you will likely be bothered by a salesperson, but given that it's a relatively large financial commitment, I'd say it's worth it. If the salesperson factor really bothers you and you live near a shopping mall, you can always swing by a Verizon kiosk and you may have better luck experimenting with phones. Kiosks are often manned by just one individual, so the odds of you getting some alone time with a phone are better.
Next, simply use the phone. As you seem pretty open-minded, try a few different ones ... a QWERTY-keyboard smartphone, a touchscreen, etc. Verizon has a pretty good selection of touchscreen devices beyond the BlackBerry Storm and Samsung Omnia, both previously mentioned. There are a few made by LG and a couple others also produced by Samsung. The responsiveness of the touchscreens will differ from phone to phone and, if that's the route you decide to go, be sure to try a few. Don't just settle for the BlackBerry because it's a name brand or go for the Omnia because it's the first one the salesperson threw at you. Pick the one that feels right.
If you decide that you aren't liking the touchscreen devices but are still interested in a smartphone, my advice there would be to find something that allows you to easily type and browse the internet. Are the keys big enough for your fingers? Is the internet application simple? Does it have a big learning curve? Obviously, each of these questions will matter more/less depending on how tech savvy you are, but it should be fairly easy for you to figure out.
Anyway, as you can see I like tech talk. If you've got any other questions, post away!