Personally I like its cousin better, http://www.engadget.com/2010/04/21/dell-thunder-explodes-android-with-4-1-inch-oled-screen-promise/ which comes with Android. Not only that, it looks like Dell tried to take the best parts of certain Android phones and incorporate them all.
That's "Plan B" if the Windows phones/support turn out to be lackluster. I'm only opting for Windows right now because I like the Zune software/interface and I like the connectivity with Windows, XBox, Office, etc. that Microsoft will hopefully put into it.
From a lot of the major publications, it seems like they are praising Windows Phone 7 to be a better phone experience than the Android and almost there with the iPhone experience. The UI is unique and intuitive IMO. It just depends on the apps now. Seems like MS is getting this one right based on early reviews.
Smallest sized screen you'd want would probably be the iPhone. Isn't its screen 3.5"? And Galaxy S line is 4", correct? Droid incredible could be a good choice if the OP is fine with a screen that is .3" smaller than a Galaxy S phone. It has a similar form factor, its on 2.2 already, and Sense is one of the best OEM skins out there. Personally, I would only get the the slide-out keyboard if you are POSITIVE you will want it. Android has voice typing and Swype, so you may ultimately find yourself not using the physical keyboard too often. If that's the case, you take on additional weight, thickness, and moving parts for a feature you don't use very often. I originally had a Droid, but I will never go back to a phone with a slide out keyboard now.
Thanks for all the info everyone. I was actually looking at W7 phones, but Verizon won't be getting any until next year. As for phones from other carriers, I've done some reading and I do like some of them, but switching from Verizon isn't an option for me right now.