These days there's not really a hell of a lot of separation between phones and smartphones, aside from a smartphone sporting an operating system that's a more "polished" and feature-rich version of that which you'd find on a regular phone. You should probably be ok with touch screens, though you can get a lot of nice smartphones with keyboards.

You can expect a smartphone to have an XHTML web browser and many come with office suites for reading word docs/excel spreadsheets, etc. A lot of them will come with GPS software and GPS services from the manufacturer. Be careful with apps like Google maps, as they'll sometimes connect automatically to your provider's data network, causing large amounts of data traffic and large amounts of dollars to be charged to you.

You'll have to choose between the five main Smartphone OSes and a few smaller ones:
- Symbian (Nokias)
- iPhone OS
- Windows Mobile (Some HTC devices, Palm devices)
- RIM OS (Blackberries)
- Android (Some HTC devices, Google's phone)
- Others (Samsungs, LGs, a few others)

I can tell you from experience, unless you like being annoyed, avoid Windows Mobile. iPhone OS is awesome but is about as closed source and proprietary as you can get. RIM OS is good, but my favourite is Symbian. I haven't tried Android but I'll lay down some ends to say that it's pretty awesome. There's a new Dell device that looks pretty awesome; and Dell have a very nice history with handheld devices (improbable, I know). And I would definitely avoid the small fry OSes here; they just haven't been around long enough to compare to the bigger ones.