A year ago I got
Nokia E51, and I still like it a lot. It's got a lot of connectivity options, and satisfies all your requirements except that it doesn't have the full QWERTY keyboard. Its regular keyboard is fantastic though, probably the best tactile response I've seen in a cell phone. The 4-way joystick with the separate, fifth "Enter" button is a total win. Most of the time, like when you want to read a text message that's just arrived or set the alarm clock, you only need to click the middle Enter button a few times (i.e., the default actions are very well chosen). Lots of memory, expansion card slot, easy wifi, USB port, and plenty of Symbian apps to choose from if you like that sort of thing. The camera's probably the only weak point, but it does record video. Can double as an mp3 player, though there are phones better equipped for that. GPS is supported but not built in, you need an add-on module.
If I were buying today, I might go for
Nokia E71, which is pretty much the same phone with a bigger screen and a full keyboard. But, it's much larger. In general, anything with a full keyboard won't fit comfortably in your pants pocket. Either that, or I'd give this
BlackBerry a close look.
I'd like to discourage you from buying a phone just on net recommendations, though. Pick a few candidates, then go to a store and hold each phone in your hand, and make sure to try the keyboard. Some (most) cell-phone keyboards are very poorly manufactured. Either they're too hard to press, or you don't feel the keys click, or the keys are too small (or
too funkily shaped) for comfortable typing. Pay particular attention to how the joystick or menu keys work, since you'll be using them the most. Nokia has a lot of models with extremely bad keyboards, but so do other manufacturers. Stay away from
touch-screens (unless you are really certain you want one) and from the Samsung phones with the flat tactile keyboards (
like this, though there are many models with the same keyboard design). Also, while a stylus looks cool, you really don't want a phone that requires both hands to operate.
Another way to choose a cell is to decide whether you'll be putting any applications on it and what kind, or if you'll need to synchronize data with your PC. Nokia smartphones are Symbian based, and while there is no shortage of available apps, they usually don't sync with anything on Windows. My favorite Calendarscope has
a number of syncing options, but Symbian is not included. You'll have better luck with anything based on Windows Mobile. So in that case first choose the OS, then find a phone to match.