I was trying to find out how I could get the font on my computer, when I discovered that the Sun Java package includes the original Lucida Sans fonts. I now make a point of installing Java on all of my computers, then copying the fonts from the lib/fonts folder into my system fonts folder.
There's a similar font that comes with Mac OS X called Lucida Grande.
Microsoft Windows also comes with a version of Lucida Sans called Lucida Sans Unicode. On some systems (e.g. Windows 2000 without ClearType) this doesn't look very good and it doesn't differentiate between normal and bold, so I only use this as a fall back if the other two aren't available.
I use these three fonts as the default fonts on my web site. Since at least one of these is included in recent Windows and Mac systems, most peeple should see a Lucida Sans variant.
It also turns out there's a number of other good fonts available for free download, starting with the Microsoft Windows Core Fonts, including Andale Mono, Arial, MS Comic Sans, Courier New, Georgia, Impact, Tahoma, Times New Roman, Trebuchet MS, Webdings, and Verdana. Most people will be familiar with these fonts, but I'd like to point out Andale Mono as it's a really good font for programming and much better looking than Courier New. They can be downloaded from the SourceForge Core Fonts Project Page.
Other worthwhile downloads are the Windows ClearType Fonts, including Calibri, Cambria, Candara, Consolas, Constantia, and Corbel. They are all included in a standard install of Windows Vista or Microsoft Office 2007, but you can also get them in the Microsoft PowerPoint 2007 Viewer package. Calibri is the definite highlight. It's the default font in Word 2007, so you're certain to see it more in future.
The Microsoft Office Fonts includes some classics, particularly Century Schoolbook, Gill Sans MT, and Lucida Sans. You can get them with most versions of Microsoft Office, but you can also get them in the freely available Microsoft Publisher 98 Euro Fonts Update. Run PubUpd.exe /c /t:c:\temp, then copy the TTF files from c:\temp into c:\windows\fonts.
I discovered today that Adobe Reader version 8 includes Myriad Pro. It's an attractive humanist font similar to Lucida Sans. It's the font used in Apple ads. You can download it here. Install it and then copy the OTF files from the Resource/Font folder into the system fonts folder.
Another set of good fonts that deserve more attention is the Bitstream Vera family. They are included as the default fonts in many recent Linux distributions, and can be downloaded from the GNOME Fonts web page. They can be used as pretty good replacements for Verdana, Georgia, and Andale Mono.
Thanks to GearedBull for releasing his excellent Wikipedia font previews into the public domain.