I started playing with this weeks ago (probably during Vitaliy's problem report). Is there any reason cost_bitmap_heap_scan shouldn't interpolate based on correlation from seq_page_cost to rand_page_cost, same as cost_index ?
I think that doing something like that is a good idea in general, but someone has to implement the code, and so far no one seems enthused to do so. You seem pretty interested in the topic, so....
It is not obvious to me how to pass the correlation from the cost_index up to the bitmap heap scan, especially not if it has to go through a BitmapAnd or a BitmapOr to get there. Maybe the optimization would only be used in the case where there are no BitmapAnd or BitmapOr, at least for a proof of concept?
I haven't been able to reproduce your test case, but I have not had the hardware or the time to try very hard. I think next year I'll have more time, but I don't know about the hardware.