The Talmud records two opinions as to the line of demarcation between latest time for reciting Mincha ("afternoon") and Maariv ("evening") prayers:
- Sunset (and yes we can go into questions of observed sunset vs. astronomical sunset, elevations, and so on, but let's assume "sunset" is "sunset.")
- Plag HaMincha, i.e. 1.25 relative hours prior to sunset.
Either opinion is acceptable, if followed consistently. (And there's a lot of discussion about what "consistently" means; the Aruch HaShulchan staunchly defends the practice of reciting first Mincha, then Maariv, at some time after Plag but before sunset.)
So either plag or sunset. It's not about "I hereby accept it as Tuesday" by saying the evening prayers Monday afternoon; it's that it's close enough to Tuesday that I can say the prayers.
However, there's the obligation to recite Shema at night; we follow the majority opinion that even if you prayed Maariv earlier, you'd have to repeat Shema "when the stars come out" -- which Rabbi Moshe Feinstein ruled was 45 minutes after sunset in New York City; it would be more minutes further from the equator, less if you're closer. (But don't be surprised to meet Rabbeinu Tam followers who insist on 72 minutes in all sorts of latitudes).
So it's ideal if you could say Maariv after "stars-come-out" so you get your Maariv and evening Shema bundled into one; all else being equal, it would probably still be preferable to say Maariv oh -- 20 minutes after sunset (which satisfies "stars-come-out" for some rabbis) than immediately after sunset (though either way you'd repeat Shema later).