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, regexes, 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