Just recently, we had a case with a partial index where the predicate was a boolean field, but the indexed field was a timestamp, sorted descending. The planner chose that index when given a query that had an ORDER BY ... DESC on the timestamp, and query times spiked several orders of magnitude. Dropping the index (which was only used by that query) caused it to drop from 2.5s to .7ms.
Yes, indexes are that powerful.
It's one thing that I find it frustrating that Postgres (which I otherwise love) doesn't offer - I understand that they don't like optimiser hints, but at least the ability to say 'keep using the current plan until I give you permission to do otherwise' would be invaluable.
One sneaky way to deal with this is to order by an expression that can't be indexed, like id+0. I've had 4 order of magnitude speed ups when that sort of query tweaking pointed the planner at the right index. (And in that case, a partial index)
[0]: http://www.pgcon.org/2008/schedule/attachments/63_BSDCan2008...
I think you are adding another entity that you must now support and that the application must specifically call.
If your application supports multiple databases, i don't think you want to have specific code to support optimization. Of course you need to do this :)
spatial indices of the R-tree variety work quite well as long as the dimensionality isn't too high (i.e., your 2D data would be good).
note: the original 1984 paper on r-trees is a good one (although the performance section is a bit weak): http://postgis.refractions.net/support/rtree.pdf
... and they're great! Postgres is very smart about using them, too, so they can be a lifesaver when you have a large table of which you only [typically] use a small bit.
I've created partial indexes over geospatial data. There are 1M doctors in the US, so answering the question "how many doctors are in San Francisco" requires a join between indexes of all doctors in the US and all businesses in SF. Using partial indexes, we carved up the country into a bunch of polygons and were able to frame the question as "how many doctors are in San Francisco in polygon 34?". Much faster.