Right now, you can "index" a field by marking it as an External Id when declaring the field. However, this only works for Text and Numeric fields.
This functionality should be exposed to Date, DateTime and Picklist* fields as well.
Right now, it requires a Case to be opened to get the org analyzed, provide repro cases, go through extensive "business justification", wait several hours between each run of the slow query (since you have to wait for the query cache to expire) before Support will finally agree to have the field indexed.
As an ISV, this is hand to hand combat since each org must be done individually. By packaging the field as an External Id, we can get all the love and happiness without the hours and hours of human suffering for each org.
* We understand that the cardinality of Picklist may be low and therefore not a good candidate for an index. But it's often the case that there are a few highly selective picklist values. So if you allow it for Text fields, why not allow it for Picklist?