Get the Motorola Droid. Hands down, two :twothumbs.
I've had an HTC 6800 (Windows Mobile 6.0) AKA: The Brick lol... an HTC Touch Diamond (Windows Mobile 6.1, which was a little better, but not much) and now I have a Motorol Droid:naughty:, I promise, you won't be dissapointed. I'm not trying to knock Windows Mobile here, but Microsoft has a long way to go before I'll buy another Windows Mobile based phone, in fact, if you will notice, they seem to be phasing Windows Mobile phones out IMO.
I just thought I had a smartphone until I got a Droid

.
Seriously though, the Motorola Droid is the closest to an Iphone you can get. BTW, I'm on the Verizon network as well. Just about any app you can think of, voice guided, turn by turn GPS (no need for a Garmin with this phone, but you will need it plugged into a power point while using this feature), Google maps built in to the phone (works just like Google Earth on a desktop) the browser speed is a lot faster on the Droid, the phone doesn't freeze up like my Windows phones did and it's just all around a FAR superior phone IMHO. It might be a little learning curve for you if you're not used to a smartphone, but it's worth it.
Casey