By how many of those hundred columns client wants to order? If number is limited then adding clustered primary key and index to each column helps.

Is there lot of changes in table, additional indexes might slow these.