1. (re: the error message) When alphabetizing a pair of things (think lastname, firstname), the first field changes the slowest.
2. Having a thousand partitions may hurt more than help. I generally recommend 20-50 PARTITIONs.
3. Let's see your SELECTs. Deciding on both partitioning and indexing is more complex than your simplistic question. Also, let's see the tentative CREATE TABLE.
4. See my tips in
http://mysql.rjweb.org/doc.php/ricksrots#partitioning
5. Your use case may be "I need two clustered indexes", which is semi-possible. That means (perhaps):
PARTITION BY RANGE (city) & INDEX(state, city)
or
PARTITION BY RANGE (state) & INDEX(city, state)
I lean toward the former since the granularity of city is better. (In many statistics, such as population, CA makes up 10% of the US total. 10% is poor selectivity.)
Pending further info (#3, above), I suggest about 50 similar-sized partitions and
PARTITION BY RANGE (city) & INDEX(state, city)
plus perhaps other indexes.
`city`, if present in an index, should be last.
If you are using InnoDB, have a PRIMARY KEY, even if it is an artificial AUTO_INCREMENT.
Perhaps all secondary indexes should start with `state`.
Do not use utf8 for state; use CHAR(2) NOT NULL CHARSET ascii, pick either ascii_bin or ascii_general_ci, depending on whether you want case folding. (latin1 would do equally well)
`city` is less obvious. Some places (eg, San Jose, CA) have toyed with adding an accent. At which point, ascii is out; latin1 or utf8 would work about equally well.