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.