This is a simple and clear issue, with a unique answer. I see other replies mentioning weather conditions, dark adaptation and so on. That's just so much hand waving, given that the first thing you said was "I've always lived in somewhat large cities".
The core problem here, by a very wide margin, is light pollution if you live in a large city. This is the one factor, above everything else, that affects your ability to see the stars.
Here's a light pollution map:
http://www.jshine.net/astronomy/dark_sky/
The white zones are the worst, and they are in the middle of the cities. Black zones are the best.
Here's a somewhat better (but not perfect) comparison of a dark sky versus light polluted sky (your picture was taken with a very long exposure that doesn't look very realistic):
![enter image description here](https://i.stack.imgur.com/M5mfu.jpg)
The dome of light above the city is very visible if imaged from afar:
![enter image description here](https://i.stack.imgur.com/1TiCC.jpg)
Long exposure pictures in cities will reveal the orange skyglow, which is the main reason why you can't see the stars - it's like noise masking off the faint light from the distant objects:
![enter image description here](https://i.stack.imgur.com/fh5Gl.jpg)
Light pollution affects primarily the observations of faint objects, such as nebulae or distant galaxies. Bright objects such as the Moon, the big planets, or some of the bright stars, are not affected by light pollution.
Using a telescope with a large aperture alleviates the effects of light pollution to some extent, but it cannot work miracles. A dark sky is always better.
Usually a 1 hour drive away from the city will bring you in a place with dark sky, free of light pollution - but it depends on several factors. In such a place you should be able to see the Milky Way with your naked eye. The Andromeda galaxy also is visible with the naked eye if the sky is dark enough.
Following the questions raised by Rob Jeffries, I have completely rewritten my answer:
What is the farthest-away star visible to the naked eye?
Indeed, this question has many defensible answers. It is not just the concept "visible to the naked eye" that is fuzzy. The stars we see are seldom single objects, but rather binary and multiple star systems. Do we allow doubles and multiples? The wording of your question ("let's restrict to individually distinguishable stars") suggests to exclude multiple star systems. But the candidate farthest visible star put forward (Eta Carinae) is exactly that: a multiple. And like most highly luminous stars Eta Carinae is also a variable star. Should variable stars be allowed? Should we allow variable stars that in the recent past were visible to the human aye, but currently are not? If so, do we also allow cataclysmic variable stars? Do we allow novae and supernovae? Apart from all these ambiguities, as stressed by Rob Jeffries in below comments, there is also the issue of (often considerable) uncertainty in cosmic distances. How do we handle these uncertainties?
Let's first define what we mean by "visible to the naked eye". Which stars are visible to your naked eye depends on the light pollution of the site you are observing from and the atmospheric conditions (and obviously also on you eyesight). A so-called "magnitude 6 sky" is often taken as the standard for a good dark site with no light pollution. The threshold stars you can see in such a night sky have apparent magnitude 6.
So we can eliminate a key ambiguity by changing the question into "which star brighter than 6th magnitude is farthest away?".
According to this article :
"The farthest star we can see with our naked eye is V762 Cas in
Cassiopeia at 16,308 light-years away. Its brightness is magnitude 5.8
or just above the 6th magnitude limit."
This answer puts forward a variable star, but clearly excludes supernovae as that would have resulted in much larger distances (more about that later). Rob questions the apparent five-digit accuracy in this answer. A bit of research reveals that the distance figure is derived from the central value in the measured parallax of 0.22 +/- 0.59 mas (milli-arcseconds). This means that we have no more than a 50% confidence that the distance is indeed 16 kly (kilo lightyear) or more.
We should not blindly accept a 50% confidence level. Rather, we should agree on a confidence level that is deemed sufficiently strict for the intended purpose of selecting the most distant star. Yet another ambiguity to resolve!
I propose to use the one standard deviation upper range of the parallax measurement (in the case of V762 Cas 0.22 + 0.59 = 0.81 mas) to derive distances. This gives us an estimated distance of 4.0 kly with a confidence of about 85% that the actual distance is at least this value. (As Rob points out, a more recent parallax measurement for V762 Cas results in 1.18 +/- 0.45 mas. If we would combine both parallax measurements to derive a chi-square estimate of the actual distance, we arrive at a value compatible with 4 kly.)
This results in the conclusion that the often quoted V762 Cas (see e.g. here and here) is unlikely the most distant naked-eye-visible star. For instance, HIP 107418, put forward by Rob as candidate most distance star, has a lower one standard deviation upper range of parallax of 0.62 mas, corresponding to a 85% confidence distance of 5.3 kly.
I do not have the means to analyze extensive star data bases, but offer this candidate most distant naked-eye-visible star: AH Sco, with a one standard deviation upper range of parallax of 0.48 mas, leading to a 85% confidence that its distance exceeds 6.8 kly.
Finally, what answer do we arrive at if we allow for a broader range of variable stars, including supernovae?
I propose SN 1885A at a distance of 2.6 million light years (!) as the most distant single star that was once (almost 130 years ago) visible to the naked eye.
Best Answer
Here is an update on (my) answer that your refer to. I have changed the visual threshold to V<6.5 mag (which is what Sky and Telescope have done) and I have used the revised Hipparcos reduction from van Leeuwen (2007) (catalogue available here) to obtain a (almost) complete catalogue of stars with their trigonometric parallaxes. It contains 7892 stars. I am not going to investigate the discrepancy with the Sky and Telecope article which uses the Hoffleit & Jaschek bright star catalogue as their reference.
The distribution of distances is illustrated in the two plots below (labelled in light years, as you wish). The first shows the number of stars as a function of distance. The second shows the cumulative fraction of stars closer than some distance. From this, you can read off, or I can tell you, that 90% of bright stars in the Hipparcos catalogue are closer than 1175 light years.
NB: I don't think 4 significant figures are warranted. There are some tens of bright stars that are so distant that their parallaxes are too small and are garbage (negative in some cases). I'm also not clear about what the status of binary stars are (you can't resolve them, but in many cases Hipparcos could)
Number of bright stars versus distance
Normalised cumulative frequency of star distance