Really can't go wrong with the blackberry.... look at the 88xx/87xx series. If you are interested in the storm find a friend who has it or go to the store and spend some time playing with it, using the touchscreen, etc.... Played with a friend's the other day along with stopping by a Verizon booth and it seems like the latest updates have improved the interface quite a bit from some of the early reviews I read but it still had some hiccups (slow screen transitions, freezes, sometimes not recognizing touch). The screen is REALLY nice on it and I think it's a real promising device. It does have the clickable screen though it seems that people either like it or hate it. That said if you've ever used the iphone multi-touch screen you'll probably be disappointed with any other screen.
Palm..... eh. Platform is getting a little stale, some are even wondering if they'll be around for much longer, we'll see.
When I stopped by a Verizon booth the other day I was looking through their catalog and saw the Samsung Saga, which I hadn't heard about until that point. It's a Windows Mobile 6 Pro touchscreen device, with physical keyboard, wifi, and I think multiple radios in it (EVDO, GSM). Haven't looked at any reviews yet but if you don't mind windows mobile then it may be an option.
So if just have to stay with Verizon it's looking like either a Blackberry device or Windows mobile. I wouldn't totally write off the Storm yet, just read some recent reviews and play with it yourself. If you don't need it know just wait for a while as more updates come out.
I'm currently researching options for when rotations start as well. Currently with AT&T so looking at the Blackberry Bold or iPhone so I don't have to switch. Leaning towards the iPhone as the interface is just soooo nice to use. Still have my old iPaq (Windows mobile) so I'm use to windows mobile but I'm kind of tired of dealing with windows mobile.