I was using Linux from roughly from 2002 to 2012, starting with Red Hat 9, trying a bunch of distros until I settled on Debian Testing for many years. So while I don't know anything about 3DFX cards and 90s gaming under Linux in general, I think, I've witnessed some of the bigger milestones that made modern Linux gaming possible.
1. What was the milestones that paved way to what Linux is today in terms of gaming?
I'd say Ubuntu was a big one, because it automated installing a lot of non-free stuff that a lot of other distros didn't ship by default. Before that you had commercial boxed Linux distros like RedHat and SuSE that did contain some proprietary software, but I think none of the free distros did. Say, original Fedora releases didn't carry proprietary NVIDIA drivers, MP3 support, Flash and TrueType fonts — you had to find a 3rd party repo (I think one of the big ones was RPM Fusion), modify X11 configuration, etc.
Next milestone IMO would be compositing window managers like Compiz and others. People really liked those rotating cubes and wobbly windows! But to use those you needed hardware acceleration! That meant that there suddenly was a big reason to mess with 3D graphics drivers besides gaming, and I think for the time some people considered compiz to be the killer app (read: something cool you could show your Windows friends). I think that kinda gave a big boost to 3D graphics support on Linux desktops — certainly to open source graphics drivers.
Later Ubuntu did another nice thing with PPAs (Personal Package Archives) which meant that they would host 3rd party repos, and those would often be used for providing upstream updates to the users of stable distro releases. Say, you need newer WINE, and somebody from the WINE team maintained a PPA with it — you could just add that PPA and get an update without switching your whole distro to testing or building the package yourself. Otherwise you'd only get new WINE
The next big thing was Humble Bundle in 2010ish. Their very first bundle was cross-platform, and that included Linux and Mac versions of games like Braid, World of Goo, Fez, Super Meat Boy and other indie hits of the time. I think this was the first case where people would see that Linux users were willing to pay for games.
Around the same time CD Project also launched GOG, and I think pretty soon they started to sell cross-platform games as well — mainly Linux titles and also DOS games that bundled DOSBox.
Two years later Steam would get a Linux version.
2. Was there any alternatives to Wine?
Not really. There were a few commercial versions of WINE, like WINEX by TransGaming and CrossOver. They didn't work too well, but they were actually used to make some commercial ports of Linux games (I think one of Civilization games was ported like that).
3. When exactly Linux received native ports of real games? Real - not some generic Solitaire/Mahjong/Whatever clones but quality stuff - earliest I've found was Loki series (e.g. Shogo, Rune).
Well, like others said, it was Doom, Abuse, Quake. I think id even tried to get Red Hat to distribute Quake 2 on Linux at one point.
Then around 1999 you would get Unreal Tournament, Civilization: Call to Power, Heroes of Might and Magic 3, Myth 2, Railroad Tycoon, etc. You can look at mobygames, they have a Linux section. Following that you would get a bunch of games using Q2, Q3 and Unreal engines — Heretic 2, Soldier of Fortune, Rune, Heavy Metal FAKK2, etc.
4. What was the best distro?
Commercial game releases in early 2000s usually came with packages in three formats — gzipped executable, RPM and (if you lucky) deb. So for the time RPM-based distros would be best in early 2000s: Red Hat, SuSE, Mandrake.
Oh, and there are no Linux Retro Gaming PC builds in the web except for this, is there really no interest in building one?
I think historically it doesn't exist. If you had gaming-level hardware at the time, you would dual-boot.
Then again, Linux gaming history is not just commercial games. There were (and still are) quite a few open source games, and not just Tux Racer! Battle for Wesnoth, oolite, Vega Strike, Freeciv/Freecol, Nexuiz, Pingus, Torcs, nethack-x11, etc. Usually clones of big name PC games and not too demanding, but could be interesting to try.