Phone showing wrong city and state location

This can occur sometimes when using 2 factor authentication. If the IP address of your device used to log in is seen as being in another location, that message appears. These login attempts that show up are actually just you signing on and your ISP routing the traffic through servers that aren't near you. Basically, you have nothing to worry about as long as this happens at the same time as you log in. Regardless, changing your password (just once is needed) ensures your security.

Where is the iPhone showing wrong city & state? For what app? maps? contacts?

Try going to:

Settings > Mail, Contacts, Calendars

Then in "My Info" under CONTACTS, whose contact is shown? Is it yours? When you tap on "My Info", is the city & state correct for you in your contacts?

OK, this is something completely different from what I first thought you were asking. If you used this Apple ID before and haven't changed it, then something fishy is going on. I don't want to alarm you, but I think you need to contact Apple Support on this one:

Apple ID - Official Apple Support