Ваш выбор может зависеть от того, что вы подразумеваете под Palatino-like и сколько вы готовы заплатить за коммерческий шрифт. Шрифт Linux Libertine с открытым исходным кодом - это шрифт с засечками, имеющий кириллические символы, но в действительности он не похож на Palatino:
http://www.linuxlibertine.org/index.php?id=2&L=1
Здесь вы можете приобрести коммерческие шрифты, такие как семейный набор разных лиц и весов:
http://www.fonts.com/FindFonts/Detail.htm?pid=4653079&/cgi-bin/MsmGo.exe?grab_id=0&page_id=12025&query=PALATINO&SCOPE=Fonts
В любом случае вы захотите использовать XeTeX (или LuaTeX), чтобы автоматически упростить использование этих шрифтов, а не простой LaTeX или pdfTeX.
Существует масса коммерческих шрифтов с наборами кириллических символов, многие из которых дешевле, чем шрифт Linotype Palatino, указанный выше (хотя даже Linotype может быть дешевле, если вам не нужны все разные грани и или веса). Для примера некоторых более дешевых коммерческих возможностей проверьте, что доступно из Литейного завода Storm Type:
http://www.stormtype.com/
или просто зайдите в онлайн-магазин шрифтов, например fonts.com, и немного побродите по нему.