tl;dr: We don't know where it's located, and apparently, neither do the writers. We have gotten a ton of contradictory information, but based on the information we've seen and heard on screen, it's either near Chicago; or else, its near Seattle, or near San Francisco, or somewhere halfway between the two.
Unfortunately, there has never been a definitive location for Starling City, either in the Arrow TV Show, nor in the source material. Like the other DC cities, it's location has remained vague, and varied as the story demanded it.
In The Green Arrow and related comics, Star City has been explained in various places over the years. Early on, it was alternately depicted as being on the East Coast (on Massachusetts Bay) or the Great Lakes (Lake Michigan). In the past few decades, it has remained largely confined to the West Coast, where it has been seen as a substitute to both Seattle and San Francisco.
In the current DC timeline, I believe Star City is located "somewhere" on the coast of Northern California, a bit north of San Francisco itself.
The Starling City of Arrow was never depicted on the Easy Cost, but otherwise, it moves around almost as much as it's comics counterpart. In particular, there appear to be at least three conflicting locations given, based on both dialogue and explicit maps of the US shown on-screen.
Star[ling] City In The Midwest
So far, we have seen two large-scale maps of the United States with Star[ling] City's location on it. In "The Climb" (Season 3), we see a map of the United States with Starling City labelled on it, and it's clearly in the upper mid-west, somewhere in the Great Lakes Area (right around Chicago)
In "Schism" (Season 4), we get a clearer map, showing the incoming nuclear missile. The missile was launched from Colorado, and is heading almost due east towards Star City, which is quite clearly located exactly where real-world Chicago is.
In addition, we know that Star City is roughly 600 miles from Central City, based on a number of comments about Barry running back and forth. In the comics, Central City is typically placed somewhere in the Midwestern United States, most often in Kansas City's real-world location. If we look at all the places that are roughly 600 miles from Missouri:
We can see that Chicago does qualify.
Star[ling] City On The West Coast
On the other hand, we have also seen a map that appears to put Star City on the West Coast:
This would make a lot of sense, since we know that Star City has a marina with access to the Pacific (The Queen's Gambit left the marina and sailed to Lian Yu, an island in the Pacific). In addition, one of the things we know about Central City in the Arrowverse is that it's on the coast of some very large body of water. We have seen multiple cases of things happening on the shore of a large bay, for example, when Barry is running Plasqitue's body out to sea before it explodes:
That means that Central City can't be in the mid-west, and is most likely on the Pacific Coast (based on Barry's direction of travel). It's possible that it's situated on a really big river, but the overhead shots definitely look like a coastal city with barrier islands and no land on the other side of the water. If we place both cities on the Pacific Coast -- and ignore the explicit maps to the contrary -- all the pieces fall into place.
Where, exactly, on the coast the city should be is trickier. Based on that map, it looks like Star City would be somewhere on the northern coast of California. Since it's due west of a city in Utah, it could be anwhere north of San Francisco. Again, these maps are (intentionally, I suspect) hard to read, but it looks like the northern end of the mountain ranges in Utah and California, which puts Star City vaguely in the area of real-life Eureka or Crescent City.
Unfortunately, there are a number of other tidbits of evidence that put Starling City much further north, in northern Washington State:
- In Season 1, Felicity gives Oliver coordinates to a building in the Glades (47.6097°N, 122.3331°W), which are in Seattle.
- In Season 2, we also get one of the zip codes for Starling City, 98114, which is also within the zip code range for Seattle.
- Felicity claims she moved "1000 miles away" to work at Queen Consolidated. Las Vegas is just about 900-ish miles from Seattle.
At this point, with the city having been conclusively placed in three totally distinct places over 5 seasons, it seems obvious that the writers are purposefully making the city's location vague. Again, this is exactly what happens to the city in the source material -- it moves wherever the plot needs it to be. This is probably the best we're going to get from the TV shows as well.