Improving query time for auto complete box with millions of record
Have you thought about restricting the search in the UI?  Don't start the autocomplete query until after they've typed 3 or 4 characters. Then instead of looking for 6000 A*, the first jump would be a fraction of that number still. 

Also, @Jonathan Fite 's comment about removing the leading % is also a good way to reduce time.  Unless, your users start looking for ew Yor, or shington...