Not as stale as the Microsoft fonts. And it has a certain class about it.
Bitstream Vera. Download it now and tell your friends about it, so people will stop bickering about the totally unimportant lack of Microsoft fonts! :) http://www.gnome.org/fonts/
Bitstream Vera rocks!
A bitmap optimised Gill Sans - or rather, a bitmap optimised font "inspired" by Gill Sans, since it wouldn't be the same, would be interesting. Perhaps one of the Macerati font wanglers could do a properly hinted version. (Half the point of the Microsoft fonts is the exhaustively tested hinting_
Bitstream Vera Serif doesn't look anywhere near as nice as Georgia, however.
Georgia is my current favorite as well.
You don't think Gill Sans is getting stale yet (as Palatino did when everyone got sick of Times)?