New Query:
SELECT * FROM media m 
WHERE m.mediatype = (SELECT objectid FROM mediatype WHERE medianame='Audio') 
AND EXISTS 
(SELECT * FROM 
(SELECT objectid AS mediaid 
FROM media 
WHERE activity='347667' 
UNION ALL 
SELECT ism.media AS mediaid 
FROM intsetmedia ism, set s 
WHERE ism.set = s.objectid 
AND s.activity='347667' ) AS a1 
WHERE a1.mediaid = m.objectid 
) 
ORDER BY medianame ASC, status DESC 

 
QUERY PLAN: 
 Sort (cost=280852.86..280857.77 rows=1963 width=218) (actual time=129360.72..129360.73 rows=27 loops=1) 
  Sort Key: medianame, status 
  InitPlan 
  -> Seq Scan on mediatype (cost=0.00..1.29 rows=1 width=8) (actual time=0.13..0.15 rows=1 loops=1) 
  Filter: (medianame = 'Audio'::character varying) 
  -> Index Scan using media_mtype_index on media m (cost=0.00..280745.48 rows=1963 width=218) (actual time=5523.85..129359.96 rows=27 loops=1) 
  Index Cond: (mediatype = $0) 
  Filter: (subplan) 
  SubPlan 
  -> Subquery Scan a1 (cost=0.00..138.91 rows=2 width=24) (actual time=2.84..2.84 rows=0 loops=44876) 
  -> Append (cost=0.00..138.91 rows=2 width=24) (actual time=2.84..2.84 rows=0 loops=44876) 
  -> Subquery Scan "*SELECT* 1" (cost=0.00..5.11 rows=1 width=8) (actual time=0.06..0.06 rows=0 loops=44876) 
  -> Index Scan using media_pkey on media (cost=0.00..5.11 rows=1 width=8) (actual time=0.04..0.04 rows=0 loops=44876) 
  Index Cond: (objectid = $1) 
  Filter: (activity = 347667::bigint) 
  -> Subquery Scan "*SELECT* 2" (cost=24.25..133.80 rows=1 width=24) (actual time=2.77..2.77 rows=0 loops=44850) 
  -> Hash Join (cost=24.25..133.80 rows=1 width=24) (actual time=2.76..2.76 rows=0 loops=44850) 
  Hash Cond: ("outer"."set" = "inner".objectid) 
  -> Index Scan using intsetmedia_media_index on intsetmedia ism (cost=0.00..109.26 rows=38 width=16) (actual time=0.04..0.04 rows=1 loops=44850) 
  Index Cond: (media = $1) 
  -> Hash (cost=24.24..24.24 rows=6 width=8) (actual time=0.14..0.14 rows=0 loops=44850) 
  -> Index Scan using set_act_index on "set" s (cost=0.00..24.24 rows=6 width=8) (actual time=0.11..0.12 rows=2 loops=44850) 
  Index Cond: (activity = 347667::bigint) 
 Total runtime: 129361.35 msec