If I remember some of our earlier conversations correctly (and being quite cheeky in speaking for him), Tommy is like a lot of Linux users and wants to stick to Linux fonts whenever possible. And well he should. It's simple as pie to include Linux fonts in your stacks -- hell, at the beginning, where they actually have a chance of being used by Linux users who may have the MS core fonts installed, and who see 90% of the Web in combinations of Arial, Tahoma, Georgia, and Times New Roman. I really like the families of Linux fonts I'm familiar with: Liberation, Deja Vu, Nimbus, Bitstream, and Luxi.
Harri, no disrespect, but your "quiz" answers are all but meaningless. It's like asking me the best dog to choose for hunting and having one of the choices "purple" and the other "Chevrolet." All Web fonts display in HTML, so that choice can be set aside. WYSIWYG is irrelevant, so that one's gone. And all fonts you're likely to see on anyone's Web pages are available on the Internet in one form or another, so that one's out. (And no one with any sense uses images as body text.)
What you're asking is what fonts are "safe" to use on the Web. In the strictest sense, the answer is "none," because there's no guarantee that every off-brand computer in the wilds of the Internet has a particular font installed on it. Even Arial and Times New Roman, with 99+% market penetration, aren't on every single machine in existence. Let me be really cheeky and send you to an article I wrote in 2009 that addresses some of what you're asking.
As for WebDonkey's question about a replacement for Interstate, it's a fairly straightforward Frutiger-like sans-serif font. You can go with the usual suspects: Helvetica, Arial, Tahoma, Liberation Sans, all the other more narrow sans-serif fonts, without any real problems, I'd say, though I can't promise the sizes will correlate perfectly. Test, test, test, and in different browsers on different OS's.