If you only need a phone for voice conversations/SMS only then any phone will do. All you need to care about is if it's not hardlocked for use in any particular cellular network. Also, if you plan to travel with it, you should buy one that supports GSM standard (most widely spread cellular standard in Eu/Russia). CDMA works too, but it's more expensive and has less coverage area.
If your interests include Internet, you'll need a communicator (to my taste, HTC makes the best ones, although some people prefer iPhone).
They usually support any cellular standard and are sold in more or less 'plug and play' state - you only need to add a SIM card to it.