Since the PostgreSQL folks are clearly against hints, maybe another random feature suggestion: If a (read-only) query is taking "too long", maybe you could launch a second copy with a different plan. Maybe even a third after twice as long and a fourth after twice as long again. Kill them all once any one returns. Trades some extra load now against waiting forever for a 'bad' query plan.
The idea obviously needs work and has probably already been suggested and dismissed, somewhere, but I thought I might throw it out there, especially with modern computers having so many cores.