The most important things are calls, texts and emails. He normally uses a Blackberry Pearl. Not being used to Windows Mobile phones I don't think I can recommend something like the Omnia (or even getting something like a Sim-free Touch HD).
I think a keypad is important to him, but not a keyboard that makes the phone bulky.
T-Mobile don't do the Blackberry Storm (not that it would be any good for him by the sounds of many reviews), and I don't know anything about the G1 Android thingy.