solution for many columns table and dynamic search query SQL SERVER database

In my system product table and sales order table have many columns , over 50 columns with over 1 milions for each.

Every day there are many action inserts, updates and selects on these table.

The broblem is in the search action response 2 -> 3s in normal , when many users active response about 5 -> 6 seconds

The search action we use Store Procedure with dynamic content in WHERE clause , because in the application there are many search text box for user input example: date, name, type, agent, issue, ....

When user input 3 condition and then in where clause have 3 conditions for searching, note that the comparison operator is 'LIKE' because user when input text-box they just want to input a fews character and then click search buttons. I have thinks about the full-text-search but it not supports the case example: the phone number is '09786958474' users just want inputs '474' or '09786' and then click search. Full-text-search can not resolve here.

I have create serveral index base on the date , orders numbers ... but you knows dynamic query so the conditions change continuity. I can not create all the index with all specific conditions because too many indexes I have problem with insert and update actions.

Any one have any experience about this problem please help me .

Thanks