There were plenty of free and open operating systems. Linux and FreeBSD had the advantage of also being similar if not the same as what they were replacing, as well as allowing a lot of the software that was designed for UNIX's to also work with little or no change. In other words, they cloned the look, feel and compatibility (well , FreeBSd didn't really clone it, it IS it).
AFAIK, any possible nebulous legal situation with FreeBSD should have been resolved by late 1994[1], which is extremely early in Linux's lifetime if we're talking about supplanting major operating systems. I think you're right that there weren't a lot though.
That said, I can't imagine Linux actually having gone very far if it wasn't a UNIX clone. I think it would have been a real long uphill battle and it would have gotten handily beat by whatever open source UNIX clone came along next, for the pure reason that it's much easier to deal with POSIX compliance (and all the software it brings that actually makes it worthwhile to run the OS) when trying to copy a system that already did it and worked out the kinks.
I mean, if someone came out with a free (maybe open source) version of Windows at that time which was legal, we could easily be living in a world where that's the dominant free OS.
I guess what I'm saying that that being vastly better on one metric (in this case, free) doesn't necessarily mean you'll take over a market (because a free operating system that can't run any software isn't very useful), and just being a clone won't either, but being a clone that's generally as good one most metrics and vastly better on a few others (e.g. a UNIX which is also free and open source, instead of just some other UNIX) may.
