From now on, this topic will no longer be about purely substitutes, but new
fonts I find in general.
And have I got a cool find! It's called Andada, and it's an awesome Spanish
slab serif designed by Huerta Tipográfica (makers of "font of the decade"
Alegreya [which is also awesome]). It's currently available only on
FontSquirrel, and the site recommends a ton of non-free fonts as well as free
ones, so I can't link to it. But you should be able to find it with your
favourite search engine and then search the site for "Andada".
If you're interested in doing these searches yourself, the places I check for
free fonts are:
Google Web Fonts (note: the Ubuntu typeface is not free software; do not
download it
FontSquirrel (but always check the license)
A site called free.type.org.ua (again, can't link as they recommend lots of
non-free fonts as well, but it's there that I found the aforementioned
Permian Typefaces that are mentioned nowhere else)
Searching the web for "[adjective] free fonts 2013" brings up lots of blog
collections of free fonts. I used this to find Roboto Slab even before Google
had released it!
Designer Pablo Impallari's website, located at [his last name].com. I can't
link to him as on his front page he recommends a proprietary font manager. He
releases his projects as betas and they're often high quality even then.
Check out the Encode superfamily he's working on now!
I don't recommend that you search sites like DaFont and 1001 Free Fonts.
Someone, I can't remember who, said of fonts on those sites "Here's a bunch
of useless junk you'll like because it's free" [gratis]. There are too many
display faces and not enough styles/weights. But if you must browse them for
serious fonts, use the "serif" category first; most display fonts are
classified under sans-serif.