pg_class has 3615 rows and 1010Mb in table size

The pgAdmin performance on one of our database servers has been dismal
for a while now. I captured one of the queries that was taking forever
to return, therefore making pgAdmin unresponsive for up to 10 minutes.

The query is as follows:
SELECT rel.oid, relname, rel.reltablespace AS spcoid, spcname,
pg_get_userbyid(relowner) AS relowner, relacl, relhasoids,
relhassubclass, reltuples, description, conname, conkey,
       EXISTS(select 1 FROM pg_trigger
                       JOIN pg_proc pt ON pt.oid=tgfoid AND
pt.proname='logtrigger'
                       JOIN pg_proc pc ON
pc.pronamespace=pt.pronamespace AND pc.proname='slonyversion'
                     WHERE tgrelid=rel.oid) AS isrepl
, substring(array_to_string(rel.reloptions, ',') from
'fillfactor=([0-9]*)') AS fillfactor
  FROM pg_class rel
  LEFT OUTER JOIN pg_tablespace ta on ta.oid=rel.reltablespace
  LEFT OUTER JOIN pg_description des ON (des.objoid=rel.oid AND
des.objsubid=0)
  LEFT OUTER JOIN pg_constraint c ON c.conrelid=rel.oid AND
c.contype='p'
 WHERE relkind IN ('r','s','t') AND relnamespace = 16686::oid
 ORDER BY relname

I looked at the pg_class table and noticed that its size is 1010Mb and
index size is 1137Mb, while the table itself has only 3615 rows in it.
I tried vacuuming it, but that did not change anything. Is there
anything I can do to get this table back to the size it is supposed to
be at?

PostgreSQL 8.2.6 on Windows 2003 Server.