Ignoring beyond 66.5 degrees north and south of the equator, where both sunrise/sunset and the related Halachos get weird, a good place to start is the Sunrise Equation. Wikipedia does a good job explaining how it works, and I’ll direct the reader there for the relevant equations and their explanations.
The important part for this question is that Shabbos starts shortly before sunset on Friday evenings. The first places on the globe to accept Shabbos would be just west of the International Date Line (henceforth IDL), and the last places would be just east of the IDL. Further, since the days are shorter and longer at the extremes (leading to the opening sentence of this post), the earliest Shabbos of the year would be at the northernmost place just west of the IDL (i.e. the tip of Siberia) on the winter solstice, and the latest Shabbos of the year would be at the southernmost place just east of the IDL (i.e. Tahiti).
However, things get confusing because you need to consider where, exactly, the IDL is. In the examples above, I assume that it’s the civil IDL, but it’s not so clear that this is the case. A more detailed discussion can be found in this question. Based on the various opinions there, the earliest Shabbos would seem to remain in Siberia, but the latest one could be anywhere between King Island (just south of Australia) to Tahiti.
To confuse things further, there’s the concept of “early Shabbos.” While commonly applied in the summer, Shabbos can be taken in at Plag any day of the year. As such, the earliest Shabbos is not sunset of the winter solstice, but the time 10 3/4 of the way between either sunrise and sunset or Alos and Tzeis (the latter opening up yet another can of worms, depending on your definition of when those times are). This problem can be avoided, at least, by restricting yourself to “on-time” Shabbos and ignoring “early” Shabbos.
One final point: I kinda lied earlier when I said that the earliest Shabbos occurs around the winter solstice and the latest around the summer solstice. You see, due to certain astronomical phenomena that I’m not going to get into right now, while those are indeed the shortest and longest days on the calendar, sunset starts creeping later a couple of weeks before the winter solstice, and earlier a couple of weeks before the summer solstice.
In conclusion, the easiest way to answer your question would, indeed, be to write an app to calculate it for you, but with the above information, you should be well on your way to doing so. Find the farthest northeast, just before the winter solstice, and plug it into the equation, and the farthest southwest, just before the summer solstice, and plug that in as well. Just make sure you’re clear on which posek you’re following when you define “farthest southwest.”