Most of the modern phones will display Cyrillic text just fine, especially the ones from the brands heavily present in Russia. In my experience, most Nokia, Sony Ericcson and Samsung models will have no issues with displaying it. Sending the SMSs in Cyrillic is a different matter. This will require flashing the firmware of the phone with a version specifically designed to have Cyrillic support. I've done it with various Sony Ericcson models, the only catch was that you would have to memorize which key is supporting which letter, since the keypad will not have them. I am not aware of a single phone sold in the US which will support that.
Anyhow, it's all fairly problematic for a non-technical person. I could recommend getting an iPhone, jailbreaking it (meaning removing the restrictions put in place by Apple to prevent installation of the third-party software) and installing a Russian keyboard from RiP (Russian iPhone Project). The next version of firmware for the iPhone, V. 2.XX, will have a native support for this. It is something that does not require any custom cables or hard-to-find software, and it is completely free.
BTW, keep in mind that Cyrillic characters are double byte, so your SMSs will be twice as short.
