You need to add indexes for whatever you filter for. Without them, every search must examine all entries in scope for the search. Include 'index objectClass eq' no matter what else, since slapd often adds an objectClass component to your filter internally.
You can use loglevel 256 to see what your clients search for.
Also messges like <= bdb_<inequality, substring, etc>_candidates: (foo) not indexed if I remember correctly.
If the clients search for (&(foo=...)(bar=...)) you might only need an index for one of foo and bar, since each 'and' component narrows down the search. If they search for (|(foo=...)(bar=...)) you need both. Even if you don't have both attributes in the database, because slapd doesn't know that. Except you don't need (and can't) index attributes your included schema doesn't define.
If you add indexes by editing slapd.conf rather than via cn=config, stop slapd and run sbin/slapindex to actually build the indexes. Without slapindex, slapd will think the empty index means nothing in the database matches the indexed attribute.