Just a hunch, but I'd guess each reader needs to have some sort of default for the 3 main classes of fonts: serif, sans serif, and monospace. If you just specify those general classes in the stylesheet, you should be safe. If you want to go a step further, the safest bets are Times, Helvetica, and Courier, which any reasonably smart reader implementation will then remap back down to whatever serif, sans, and monospace font it has available. But of course, that makes a pretty big assumption about how the reader will actually work.
As far as embedding fonts, the
TeX Gyre collection has decent clones of some common typefaces, and their license seems to allow for free redistribution.