Best Way to Partition By City / State in MySQL 5.5
Why not add two indexes: 

a) A two column index for (state, city) - handles queries for state only, then state and city 

b) An index on city - queries on cities only 

To tune for performance further you may be able to add lookup tables for state and city then use numeric keys to speed up query performance.