Case Sensitivity and Indexes

I have a SELECT statement that needs to be able to act on the data in a case
insensitive manner. In order to do this, I am using functional indexes
UPPER(field)=UPPER(val). However, this only lets me use a 1 field index in
my search.

So, to my real world example, if I have

SELECT * from customers WHERE UPPER(city) LIKE 'PARIS%' AND UPPER(state)
LIKE 'Texas%'

the query parser will chose my UPPER(city) index. However, to get the
optimal performance from this query, I need to be able to create and use an
index that is more like (UPPER(city), UPPER(state)) -- because of course my
fictional PARIS city exists in more than one state. I've considered useing
an index that concatenates city and state in upper case, but that limits by
ability to run LIKE searches on both fields. Any ideas how to make this run
faster. (btw, the query is already fast, but I want to be able to show my
users the blazing speed I know is possible in psql.)

Thanks for listening