There are more commonly-available fonts than just the standard web-safe ones, so don’t hold back completely. With body text there are two key requirements: legibility at small sizes and consistent line lengths. Obviously, there’s no point in using a font that it can’t be read at small sizes. The line length issue is a little less obvious, but remember that you’re building lists of substitute fonts. Each one is listed in case the one before it isn’t available. If you use a typeface that sets particularly tightly but the next alternative sets very wide that could mess up the structure of your page.
Book Antiqua and Bookman Old Style are almost as clear on screen as Georgia, and they’re present in any machine that has Microsoft Office installed. Use these as fallbacks for Georgia or as first-level alternatives in their own right. For completeness URW Bookman L can be specified to cater for the Lunix set. Palatino is another option; list this as Palatino Linotype in Windows, Palatino on Macs, and URW Palladio L on Ubuntu Linux.
For sans-serifs, Lucida Grande is found on every OS X-based Mac and Lucida Sans Unicode and Lucida Sans on every modern Windows-based PC. For a more striking alternative, use Century Gothic (URW Gothic L for Ubuntu Linux). This geometric sans is a Mac OS and Microsoft Office standard that works well for large book sizes and headings.