It is expensive. In some contexts the all_party_privilege_map can result in much better query plans (almost always in the PostgreSQL case).
This has to do with the use of UNIONs in the two views. In general, UNIONs in subselects will hose the Oracle and PG optimizers in many cases. Consider these two views definitive proof of that. As you've noticed indexes are ignored. There's no index on the *UNION* of the tables that themselves are indexed and the two RDBMSs seem incapable of "dipping down" into the UNION clauses and refactoring the subselect in a way that would make use of the indexes.
Whacking away at the permissions system is something I've put on my plate for 4.7. I've got a bunch of ideas floating around but it's going to take a lot of playing with real datasets and query plans to get much traction on the problem - we can't just toss the permissions system overboard.
If you want to start whacking away at it I say "good luck" and "hooray" in the same breath.
