Cyrillic, Palatino, and xelatex

This can be easily done with any variety of free Palatino-like fonts. My example below uses my own typeface (Tex Gyre Parliamentary, which is Palatino with different quotation marks), but the cyrillic characters in Tex Gyre Parliamentary are simply copied over from D B Miller's Domitian, which is also freely available under the same open licence. With this, and using Babel or Polyglossia, you can simply type in Russian, as normal. See this example:

documentclass{standalone}
usepackage[russian]{babel}
usepackage{fontspec}
setmainfont{TeX Gyre Parliamentary}
begin{document}
    Привет
end{document}