I tried generating a document using Palatino fonts using the 'palatino' and 'mathpazo' packages, and the resulting document did not look good at all. There was something wrong with the font hinting that caused characters to vary in size, making it look like the text was written by a child. After doing some digging, I found the Latex Font Catalogue, which lists many nice fonts which can be used instead of the default postscript ones. A particularly nice font is the Tex Gyre Pagella font, which is based on the URW Palladio font.
The main reason to use Pagella is that it is currently under development by the TeX Gyre project, and so we can only expect the fonts to get better. The project page claims that the pagella fonts are a heavily extended version of the URW fonts.
The Tex Gyre fonts are currently missing in the Kubuntu Gutsy TeX live 2007 release, so I filed a a bug report asking for them to be included in Ubuntu. It doesn't look like they will be added to Gutsy, so I've created my own .deb package that can be used to install the fonts on Ubuntu. Feel free to download the package if you're impatient like me and don't want to wait for the next release of Ubuntu.
You can manually install my TeX Gyre package by doing:
$ wget http://iml.ece.mcgill.ca/~stephan/files/texlive-fonts-texgyre_sb_02.deb $ sudo dpkg -i texlive-fonts-texgyre_sb_02.deb
The fonts included are: