You still end up in the OS/2 situation - even if non-native apps didn't always run great, had much worse memory usage, didn't feel native, etc... they were still good enough that nearly nobody (comparatively) wrote native OS/2 apps. It's not impossible to imagine an alternate past where OS/2 had worse DOS/Windows compatibility and ended up more successful! (In actuality, I think it'd probably have done even worse — showing that the strategic options to replace the foundation of an entrenched ecosystem are "bad" vs. "worse".)
I'd like to see other paradigms explored, too, but it seems unfortunately hard to get there from here.
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.
I'd like to see other paradigms explored, too, but it seems unfortunately hard to get there from here.