As a follow up to the answer regarding Tzeis my question is how does one know that the stars they see are small ones? Is there a way to determine this other than a time predetermined by the calendar?
In reality, the way R' Shneur Zalman from Liadi understands the Shu"t Maharam MiRottenberg, already in the Maharam's times the average person wouldn't know what's a small star and what's a large star.
Moreover, according to the first opinion of Tosfos (Shabbos 35a D"h Trei) (which is mentioned in the Gra (Yoreh Deah 262:9)), we (going all the way back to Rabbi Yehuda Bar Ilai from the time of the Mishna) aren't sure what's considered a "large star" or a "small star", so there are other ways given to tell Tzeis - the amount of time it takes to walk 2/3, 3/4 or 4 Mil after sunset.
This page cites Ramba"m Yesodei Hatorah. See the editor's note, as he has a valid point. I'm not suggesting that Rambam's evaluation would fit with today's common halachic practices. But, it offers one opnion in answer to your question.
Yesodei HaTorah 3:8
Among the stars that we can see, there are small ones (which were believed to be smaller than the Earth) and large ones that are much larger than the Earth. The Earth is about 40 times the size of the moon; the sun is about 170 times the size of the Earth. Therefore, the sun is about 6,800 times the size of the moon. None of the other stars is as large as the sun, nor as small as the planet Mercury.
Editor’s note: I am not able to explain the Rambam’s astronomy. In Hilchos Kiddush HaChodesh (17:24), he says that it is based on the science of Greek astronomers. In Moreh Nevuchim, he is willing to disregard Talmudic dicta (3:14) and even Biblical verses (2:25) in favor of observable science when necessary. Readers are free to assume either that the Rambam was sharing the best science of his day, or that he is describing spiritual rather than physical phenomena.
There is a debate on how one calculates this in terms of time. From here:
great Rabbis of the previous generations (especially Rav Tukachinkski zt"l) calculated that these three stars (and the absence of red in the western sky) occurs 32 minutes after sunset in winter, and up to 38 minutes in summer. This is when the sun is 8 degrees below the horizon. This calculation of 8 degrees below the horizon is used in many (most?) countries - and comes out to 50-60 minutes in Europe and America. It gets longer as one goes north.
There are other opinions - such as the Chazon Ish who fixed it at 45-50 minutes after sunset. Or those who act according to Rabbenu Tam, who wait 72 minutes.
My analysis of the above - The mentioning of red in the sky is the only visible phenomenon mentioned among the various opinions. Thus, Venus tends to be the first star that is visible and you will see it while there is still a good amount of light on the horizon. That would classify as a "big" star. So, at the least, you'd have to wait until all the "red" is gone - most likely, you'd be waiting a bit longer.