You could still use a <select> box...
But have a few of them in a row (let me explain).
The first one, you could have listing the starting letter of the company.
then have an onChange function on the select box to submit that form which would reload the page and display another select box with the categories etc....
The each time the page is loaded just filter the database results using WHERE=$someVar.
I am sure there is another way using AJAX to get it to work without having to reload the page, but i havent started to look at that...
If you do do this, dont forget to $_POST all the variables in the form otherwise they will be lost on the reload.