I'm in love with the
Free UCS Outline Fonts from the GNU Project.
They may not be as beautiful as Palatino or some of the other fonts mentioned here, but they are extremely crisp and very, very legible. In fact, "Free Serif" is the first serif font I have no complaints about when used on that 600x800 e-ink screen.