Slow enumeration of schemas and tables in a largish database
This can also be a shortcoming of pgAdmin. There have been a number of improvements for recent versions. Which one do you use? 1.14.2 is the current version (as of 2012-05-21).

Are queries from the command line interface psql slow, too?

Apart from that, you need to keep vacuuming all your tables in the database, not just pg_tables. I would strongly advice to enable the auto vacuuming daemon.

Also, pg_tables is not relevant at all. It is a system view to implement the SQL standard information schema. The relevant system tables would be pg_namespace, pg_class, pg_attribute and others. But it is pointless to target just one of them. For your kind of setup you need to be vacuuming the whole catalog. And it is very advisable to vacuum all of your database on a regular basis anyway. So, let me repeat: use autovacuum.

For starters, you can run in a Debian shell:

vacuumdb -afz
reindexdb -a
reindexdb -s


The last line targets system tables for possible bloat of indexes in the catalog in particular. See man reindexdb or the fine manual.

Finally, another option would be to upgrade to PostgreSQL 9.1. There have been a number of improvements for VACUUM and ANALYZE (among many others). In particular VACUUM FULL has been rewritten for 9.0 and does a much better job now.