Since the Lucida fonts distributed with the OS are not redistributable when
alone (and thus not open-source), what alternatives are available?

I suggest the Liberation font family.