What Dogmush said. Including the keyboard thing. I swore I would never use, or be able to use a virtual keyboard, but the one on my Evo is big and REALLY easy to use, especially in landscape mode.
I thought I read recently (either Engadget or Phandroid) that AT&T has an HTC phone similar to the Evo. You should go in and give that virtual keyboard a test drive. Regardless, I highly recommend getting one of the larger, ~4" screens. They are really not bulkier than the smaller phones. In fact for my hands, the bigger phone is a really comfortable fit. I have a friend who has the Droid X, and we both get comments from people about how much they like, and how much of a difference the bigger screens make for web browsing compared to their smartphones with smaller screen real estate.
FWIW, I've heard some good reviews about the Windows 7 phones, but I have no experience with one. Android really does seem to be taking a dominant role in the market though.