Do you have any particular preferences? Since you aren't from the USA, you aren't locked to a carrier, I'm guessing, and can buy whatever phone unlocked and shove in a sim card. Right now there are only two viable smartphone OSes: Apple's and Google's. Everything else is dross and Blackberries are just as shitty as Nokia, only pricier. There's a niche OS by Samsung called Bada, but it's not mature enough and I doubt it'll see much developer support, so that's not the smartest choice IMO. Windows Phone 7 could be nice, but it's not yet out.
The high-end international Android line-up is the Samsung Galaxy S, the Motorola Droid Pro/Milestone 2, the Sony Xperia X10 and the HTC Desire. Only the Pro/Milestone 2 has a keyboard so if you're allergic to virtual keys that would be your sole choice, but I'd advise taking a look at
Swype, which is a perfectly capable virtual keyboard and faster to type with than many hardware keyboards once you're past the learning curve. The Samsung has one of the best mobile GPU chips, so pick that if you plan to play [strike]Avatar[/strike] Smurfs HD or Sims 3 on it, but beware the cheap plastic chassis. If not, most high-end Android phones have similar specs: 1 GHz processor, 512 MB of RAM, etc. The Desire loses out somewhat for having tiny internal storage and a blargh GPU. If budget is a concern, take a look at the Acer Stream or Acer Liquid E. High-endish specs but without the price tag. Can't recommend the Sony, because the touch sensor is shite and OS updates are way too slow in coming; the X10 is still running Android 1.6 when everyone else is already on 2.2.