I need to securely store lots of sensitive contact information and
notes in a (MySQL or other freely available) database 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 simple PASSWORD
style encryption
of specific fields would not work.  (For example, I need to encrypt
contacts' names, but need to be able to sort 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.  An encrypted file system is not really an
option, because the goal is to prevent loss if the database server is
hacked (in addition, I wouldn't be able to install an encrypted file
system on the database server).

What are my options?

Ignoring the fact that it is Mysql.  In general you would have to
encrypt the data and then acess it with an unencrypt function so you
could sort it.

eg select ... from... where ... order by function_to_un_encrypt(column) asc...

That means the sort could be slow since the database will have to
unencrypt the data to sort it.  (depends upon how fast or slow the
algorithium is)  You could also do:

select function_to_un_encrypt(column),... from... where ... order by 1 asc...

I am assuming that mysql supports this syntax and I am assuming that
you can write a stored function in mysql "language".  These are things
I do not know.  I have used other databases and this would work,
albeit performance could be poor.