Lots of things to consider. This is exactly the scenario I'm working on a guide for, but it's not started yet so in the meantime...
1) Compile the code with XREF. Check the indexes that are being used are sensible indexes. Also check you aren't getting WHOLE-INDEX reads where they aren't necessary.
2) Make sure -tablerangesize and -indexrangesize are set appropriately for your database. These are server startup parameters. They are documented in the documentation. Once they are sized correctly you can use promon, or better, ProTop (
http://www.dbappraise.com/protop.html) to analyse the reads of a given query. You can then use this to tune the query.
3) Try not to have functions in your WHERE clause. But definitely don't have them on the left hand side eg "WHERE INT(somefield) EQ 1234".
4) Don't have lots of ORs. If your query has lots of ORs, load the values want into a temp table and join that.
5) If the programs are updating the database check your transaction scoping is nice and tight.
6) If your queries are based on user input then you may find a dynamic query is of use as you then only use the filters provided rather than all of them.
There's loads and loads in this area to consider, but that should keep you busy for a while!