My understanding is that their native speakers are either Yanks who don't need work permits (i.e. spouses of EU citizens) or Yanks who have a Polish passport from parent/grandparent.
That's right. There are already more than enough Americans like this in the larger attractive cities to cover any eventual job openings. There isn't much incentive to hire someone who needs a work permit fresh off the plane on a real work contract basis when they can hire someone who doesn't need a work permit on a "garbage contract" basis.
Warsaw or Wroclaw would be good large city choices for Poland.
I highly advise against Warsaw and Wrocław. They're swarming as it is with native speakers who will work for peanuts, and they are the two most expensive cities in Poland to live in, so that you pay won't go very far. The same is true for Kraków, and, to a large extent the other popular attractive cities like Poznań, Gdańsk and Toruń. All of these places have huge university populations that produce loads of unemployed English philology students who give private tutoring for peanuts, as well, so that further depresses the private tutoring market.
Rule of thumb: if you can find a place featured in a tourist guide, competition there is going to be fierce. I'm very happy that I spent the first four years in Poland out in the provinces. Better to be a big fish in a small pond than a small fish in a big pond, especially at the beginning. If I had moved directly to Wrocław, I don't think I would have lasted, and that was in better times than now.
The big, attractive cities like Wrocław, Warsaw and Kraków are wonderful to live in if you have enough cash to take advantage of what they have to offer. Otherwise, they're just as gray and depressing as Katowice and £ódź.