I spent hours researching your exact question and the VZW Blackberry 8130 has truly been the answer.
It is small while still being typable. It's the size a phone should be, not a bloody laptop in your pocket, no holster required. Great signal reception, clear calls, an easy broswer. The trackball is handier and more intuitive than a stylus. The bigger 8830 is nice, but unless you spend most of your time outside the country AND are willing to pay through the nose for an international calling plan, it's too much phone for most people. The 8130's music player is nice, CNet says it's not bassy enough but they are wrong, deaf, or both. Takes a microSDcard up to like 8gb with the latest firmware.
Heh, I just reread your question and saw you were looking for a Windows OS. I haven't run into any limitations with the RIM OS. To the user it works pretty much like Windows, the learning curve is almost instantaneous. In fact it does things that I wish Windows XP could do, like instantly extract phone numbers from an email or text message. It's designed to bridge the gap between a phone and a computer, and does the job fantastically. Unless you have specific Windows applications you plan to run, keep your options open.