Obtain the free file from the US postal service. It is available at http://federalgovernmentzipcodes.us/ and consists of a single .cvs file for more than 42,000 cities and states by their zip codes. It also contains several other columns but once in Excel, I just delete these. Open it with Excel and format it as a Table. Then use PowerQuery to separate the table into 3 tables of no more than 15000 rows each. Save each table with a different name in the same Excel file. I made mine Table1, Table2, and Table3. The reason for splitting the large table into three smaller ones is because PowerApps has an import limit of 15000 items for Static files.
Open one of your apps and add the 3 tables using the add Static files from Excel connector. This takes seconds to do.
For this example, I used a file of free sample data for testing from the internet, so the names and addresses are bogus. https://www.briandunning.com/sample-data/
Put a button on the screen and set the OnSelect property to Collect(zips, Table1); Collect(zips, Table2); Collect(zips, Table3). (If you use this formula in the OnStart property of the App, it will always be available and you don't need the button.) Moreover,creating this collection from Static tables only takes a few seconds and the user won't notice.
As you can see, the resulting collection consists of 42,522 rows and is called zips. Now where ever a zip code is found in your own dataset, you can use the LookUp() function to display the city and state. So, in the example, the Zip Code is abbreviated zip in the bogus datasource. In the gallery, I placed a City and State label, with the Text property as follows.
LookUp(zips, Zipcode=ThisItem.zip, City) & ", " & LookUp(zips, Zipcode=ThisItem.zip, State)
To maintain the 5 digit format with leading zeros, wrap ThisItem.zip as follows
Text(ThisItem.zip, "00000")
This will preven PowerApps from stripping the 0 as shown in the example for Venere, Art.
Once you have the static data in your app you will never need to enter City and State again as you can look it up from the Collection.