What's the best way to lookup the US county a US city resides in?

You can download a freely-available database of county/city/zip code info such as this one: http://www.unitedstateszipcodes.org/zip-code-database/ (no need to register or pay)

Import it whole, or a subsection of it, into a local, persistent data store (such as a database) and query it whenever you need to look up a city's county

Note: County info has disappeared from the originally-linked .csv file since this answer was posted. This link no longer contains county information: http://federalgovernmentzipcodes.us/free-zipcode-database.csv

1) Cities span counties

2) Zips span both cities and counties, not even on the same lines

Any solution that uses zip as an intermediary is going to corrupt your data (and no, "zip+4" won't usually fix it). You will find that a city-to-zip-to-county data map (#2) has a larger number of city-to-county matches than the more accurate model (#1)--these are all bad matches.

What you're looking for is free census data. The Federal Information Processing Standards (FIPS) dataset you need is called "2010 ANSI Codes for Places": https://www.census.gov/geographies/reference-files/time-series/geo/name-lookup-tables.2010.html

Census "places" are the "cities" for our question. These files map "places" to one or more county.

It will not be easy to use geospace functions for this task because of the odd polygon shaped of counties and the point locations of cities.

Your best bet is to reference a database of cities and their respective counties, though I don't know where you could find one. Maybe Texas publishes one?
CommonDataHub doesn't contain this information.