For any select list of over a couple dozen options, free-text search with autocomplete support is the only sane option.
This is a common pattern seen on real estate sites (Zillow, Redfin, etc) and travel sites (AirBnb, Kayak, any airline, etc.) Kayak shown below.
Fred Meyer (big-box retailer) has a 'Select Store' search box to solve this - requesting you narrow by zip or city, then presents a long list of matches. Free text with autocomplete would be a much better experience, but if engineering costs are a limitation this might be an option. https://www.fredmeyer.com/:
The dupe DasBeasto posted above gives an excellent, thorough answer as well.