Transparent encryption in PostgreSQL?

Greetings,

I need to securely store lots of sensitive contact information and
notes in a freely available database (eg PostgreSQL or MySQL) that
will be
stored on a database server which I do not have direct access to.
This database will be accessed by a PHP application that I am
developing. However, I also need to be able to search/sort these data
with the database functions (SELECT, ORDER BY, etc) so encrypting on
the client side (web application) or using encryption of specific
fields
would not work. (For example, I need to encrypt
contacts' names, but need to be able to search for results by name).
(I
realize I could load the entire table into memory with PHP and
process/search/sort it there, but
that's obviously not a very good solution). Ideally I would like to
encrypt entire tables. I read something about the pgcrypto contrib
module, but have't been able to discern if it can do ecryption in a
transparent way (e.g. so that I can do regex searches on the data).

My sense is that this is a difficult problem. However, I made the
mistake of promising this functionality,
so I'm scrambling to figure out some kind of solution. Any
suggestions?

Thanks so much!

Matt