When is earliest a person is allowed to daven maariv after Shekia in Eretz Yisrael? Some shuls seem to wait 15 minutes, while others seem to wait past half an hour?

There are indeed various opinions each based on different calculations of how much time elapses between Shkiah and Tzet Hakochavim. Therefore you have encountered different times when people start Ma'ariv. The opinion of the Geonim is that the time to elapse between Shkiah and Tzet Hakochavim is at most 18 minutes. According to Rav Shne'ur Zalman's interpretation of the Geonim the time is 24 minutes. There is also the opinion of Rabbenu Tam that Tzet Hakochavim is 72 minutes after shkiah. For a thorough understanding of this subject see "Jewish Chrononomy" by Prof. Yehuda (Leo) Levy. Also, depending upon your location upon the globe there may be other opinions of your local Rabbi.