I have been using Linux for a good few years now, and being free of Microsoft and Apple has opened to me a world of free fonts. Like all Linux stuff these can be a little rough around the edges, but there is enough quality for that not matter, and also there is that Linux phenomenon of the creative enthusiast who gives away their software.
If you fancy breaking out of the Times–Helvetica (or Times–Arial) mold, you might want to take a look at this PDF that displays usable text fonts (not the decorative stuff) and links to the websites from which each is downloadable. All the fonts will work on Linux, Microsoft and the latest Apple machines and are offered gratis by their creators; many of them are also libre, but some are restricted by licence.
The PDF guide to free fonts is available from http://www.garzo.co.uk/documents/freefonts.pdf.