When is the earliest time you can Daven Maariv on a weekday?
If you follow the "plag distinction", then Mincha can be davened until 1.25 relative-daylight hours before sunset, and Maariv any time after that.
If you follow the "sunset distinction", then Mincha can be davened until sunset, and Maariv any time after that. I believe there are those who will allow Mincha until 11.5 or 13.5 minutes post-sunset, if you're really in a pinch, too.
The Gemara says either distinction is okay; some say that means a shul can do one way half the year and another way half the year; some read it that on any given day, you can do either way. The most extreme version is to do Mincha after "plag" but Maariv before sunset; some shuls do this (Magen Avraham says it's okay for a community but not an individual), Aruch HaShulchan staunchly defends it, but it doesn't appear to be well supported by the sources (at least for an individual). There are other ways to stretch it, e.g. using Magen Avraham's calculation of relative hours.
Now the evening recitation of Shema must be said after "tzeis hakochavim", when the stars come out. Depending on your latitude and which rabbi you follow, let's call this very roughly 45 minutes after sunset (so long as you're no further from the equator than New York City). (Yes I know someone is going to vote me down for not requiring 72, "Rabeinu Tam.") The definition of "tzeis" is a very very complicated topic, so I'm oversimplifying here.
You can simply daven maariv right after sunset and then say Shema again later; ideally you could wait a bit so that the Shema of maariv would fulfill the evening-Shema mitzva. If you don't daven maariv until 45 after sunset you're all set for the night; if you do it in between (let's say 18 after sunset) you should still repeat Shema, but it has some advantage as you fulfilled your obligation according to some opinions.