would indexing them make the queries faster?
Um.... Yes? Since this is an equality match search, non-clustered indexing (presumably a single index spanning state and city in that order) would help hugely if there are a non-trivial number if rows in that table.