(from various-potentially inaccurate sources)
At the end of 2000 Half life had sold about 2 million copies.
Warcraft has sold at least 1.3 million copies. The bnet version and budget pricing would have increased this, but not by a lot. This also excludes considerable Mac sales
In 1999 i think SC had sold 1.6 million copies (excluding broodwars add on and battlechest). I would imagine all up it comes very close to HL.
The MS Flight Sim series dwarves HL with sales in excess of 17 million( yes, i know it started in 1980, but it's still pretty impressive-2.8 million copies in 1999 alone)
As an individual game Mysts sales of 4+ million make it the biggest seller from 1993-1999 (i have no stats for 2000, but i guess Diablo 2 must be in the running now?)
In terms of popularity- it takes a lot to beat HL (and especially CS). Flight Sim isn't played online of course. Starcraft is more popular in South Korea (about as many sales there as USA). Basically WC, SC and HL are all groovy and popular games.