What best combination of fonts for Serif, Sans, and Mono do you recommend?

I prefer a combination of Linux Libertine for serif, Inconsolata for monospace and Calibri or Linux Biolinum for sans serif. Linux Libertine is burgeoning and has nice ligatures, swashes and all that, including a rather pleasing swashed capital Q. Prior to Libertine, I favoured Cambria for serif, considering it unusual but professional, but eventually decided that its serifs were far too heavy. I also considered Cambria unsuitable from the outset as a maths font, to the point that back when I used Word 2007 I fell back on Microsoft Equation Editor 3.0 (i.e. the equation object available in Office) rather than the built-in equation editor. I'm not sure what font it uses but at the time I considered it nicer than maths set in CM.

Both Inconsolata and Consolas are top-notch monospace fonts.

Palatino, Bera, and AMS Euler

I have really been enjoying AMS Euler as a math font lately. If you need completely free fonts, then I think that Palatino + Euler + Bera Serif/Sans/Mono for code, etc. is a pretty workable combination. (This is essentially the default combination used by the ClassicThesis package.) Both Palatino and Euler were designed by Hermann Zapf and work quite well together.

This combination can be used in almost any LaTeX installation, making it a viable combination for the arXiv for example. One must be a little careful to scale the Bera to match the x-height of the Palatino though, or it looks quite strange, but once this is adjusted, the combination looks quite reasonable. (Palatino Sans would probably be the best match, but is not "free".)

\documentclass{scrreprt}
\usepackage[scaled=0.88]{beraserif}
\usepackage[scaled=0.85]{berasans}
\usepackage[scaled=0.84]{beramono}
\usepackage{classicthesis}
\usepackage[T1]{fontenc}
\usepackage{mathpazo}
\linespread{1.05}
\usepackage[T1,small,euler-digits]{eulervm}

\newenvironment{note}[1][Note:]{%
  \par\vspace{0.5\baselineskip}%
  \sffamily\small\linespread{1.05}\selectfont
  \noindent\ignorespaces%
  #1
}{%
  \vspace{0.5\baselineskip}%
  \par\noindent\ignorespacesafterend%
}
\usepackage{listings}
\lstset{basicstyle=\ttfamily,breaklines=true}

\setkomafont{disposition}{}
\setkomafont{section}{}
\titleformat{\section}
            {\usekomafont{disposition}\usekomafont{section}}
            {\llap{\textsc{\MakeTextLowercase{\thesection}}\hspace{0.7em}}}
            {0pt}
            {\usekomafont{disposition}\usekomafont{section}\spacedlowsmallcaps}

\newcommand{\I}{\mathrm{i}}
\begin{document}
\chapter{Introduction}
\section{Palatino and Bera with Euler}
This style use Palatino for a body font, with $AMS\ Euler$ font for math: $y =
\sin(x)$:
\begin{equation}
  y = \int_0^x\cos(x)\,\mathrm{d}{x} = \frac{e^{\I x} - e^{-\I x}}{2\I}
\end{equation}
Both fonts were designed by Hermann Zapf and work quite well together
as long as you use the small characters --
\lstinline|\usepackage[small,euler-digits]{eulervm}|.  Code listings, etc. can
be typeset with \texttt{Bera Mono} to give it a slightly different feel.  Again:
you must be careful to scale this appropriately --
\lstinline|\usepackage[scaled=0.88]{beraserif}| and
\lstinline|\usepackage[scaled=0.85]{berasans}|, and
\lstinline|usepackage[scaled=0.84]{beramono}|.

\begin{note}
  I sometimes use Bera Sans for extended admonitions like this one so that they
  can quickly be separated from the text.
\end{note}

\end{document}

The Google Font Directory is worth browsing. It’s targeted at web authors but many (all? didn’t check) of the fonts found there are published under SIL license and thus can be used in other projects as well.

One font (also found there) that I really like is Vollkorn which has a nice, rounded, distinctive look that is still very readable.