The Sith may have never outright ruled the Galaxy Far Far Away prior to the Republic, but they certainly ruled large portions of it on multiple occasions. The term Sith Empire refers to many attempts by Sith Lords to establish their dominion over the GFFA, from the original empire established by the Sith in the Unknown Regions - which came to encompass much of the Republic during the Great Hyperspace War - to the empires of Exar Kun, Revan, and eventually the empire of Darth Krayt.
None of these polities, nor the small Dark Jedib kingdom that sprung up during the Hundred-Year Darkness, however, seem to pre-date the establishment of the Galactic Republic after the Unification Wars (there is very little detail on these, and they end up being retconned out of existence along the line), nor did the Sith even succeed in toppling the Republic until Palpatine cleverly destroyed it from within. It is possible that Mace Windu was simply referring to the Sith ruling a large empire, rather than over the territory of the Republic itself.
To answer your second question, the Rule of Two is a relatively recent Sith invention. Prior to its establishment following the New Sith Wars, the Sith had an order, much like the Jedi.