Query Index question
If you are unable to adapt the queries, some of these columns in the where clause will remain not sargable.

To make your query sargable, You would need to try and remove the DATEADD() functions in the where clause, around Col146. 
This makes the (possible) index on Col146 not sargable.

Consider this as a possible change:

AND Col146 &lt;= DATEADD(dd,-@P4,CAST(SUBSTRING(@P1, 1, 4) + '-' + SUBSTRING(@P2, 5, 2) + '-' + SUBSTRING(@P3, 7, 2) + 'T00:00:00.000' AS DATETIME)) 
AND Col146 &gt;= DATEADD(dd,-@P8,CAST(SUBSTRING(@P1, 1, 4) + '-' + SUBSTRING(@P2, 5, 2) + '-' + SUBSTRING(@P3, 7, 2) + 'T00:00:00.000' AS DATETIME)) 


Making sure that all functions are applied to the variables. You should not take my word for it and double check this.

Index changes.

If you could make your query sargable &amp; the sort is not expensive.

CREATE INDEX IX_Table1_Col39_Col146_Col75
ON Table1(Col39,Col146,Col75)
INCLUDE(Col18 
,Col31 
,Col30 )
WHERE Col18  IS NOT NULL


However, If a lot of rows are returned after the search predicates, you might have to index your SORT (Order by) As well, since that one will use a lot of CPU depending on the  amount of rows passing through. We would have to see an actual query plan to determine this.



We are not able to change the query, no matter how much we beg and plead for mercy

You could try and index that what is sargable and try to remove the SORT operator.

CREATE INDEX IX_Table1_Col39_Col75_Col18_Col31_Col30
ON Table1(Col39 ASC ,Col75 ASC ,Col18 ASC,Col31 DESC, Col30 ASC)
INCLUDE(  Col146 )
WHERE Col18  IS NOT NULL;


Note that the &lt;> operator is not that sargable, you could probably try and change it to;

CREATE INDEX IX_Table1_Col39_Col146_Col75
ON Table1(Col39 ASC ,Col18 ASC,Col31 DESC, Col30 ASC)
INCLUDE(  Col146,Col75 )
WHERE Col18  IS NOT NULL;


What about the other columns?

The include list is something I will leave to you, depending on the expected resultset's, the key lookup could be something to live with or not. 

The optimizer might not even use the index if it thinks that the key lookup would be too expensive.



Testing the theories

To see if what I am saying holds any truth, I conducted a test, ofcourse, YMMV. It is simply to see if it is even possible to remove  the SORT operator and that we are able to seek on certain filters.

DDL + DML Below.

Index #1

CREATE INDEX IX_Table1_Col39_Col75_Col18_Col31_Col30
ON Table1(Col39 ASC ,Col75 ASC ,Col18 ASC,Col31 DESC, Col30 ASC)
INCLUDE(  Col146 )
WHERE Col18  IS NOT NULL;


While we are able to seek on col75 and col39, the sort + residual predicate remains:



And that is not what was expected unfortunately.

There is light at the end of the Tunnel (Index #2)

CREATE INDEX IX_Table1_Col39_Col18_Col31_Col30
ON Table1(Col39 ASC  ,Col18 ASC,Col31 DESC, Col30 ASC)
INCLUDE(  Col146,Col75)
WHERE Col18  IS NOT NULL;


I can rerun my modified test query (without all the selected columns)

         Declare
        @P0 VARCHAR(8000)
        ,@P1 VARCHAR(8000)
        ,@P2 VARCHAR(8000)
        ,@P3 VARCHAR(8000)
        ,@P4 INT
        ,@P5 VARCHAR(8000)
        ,@P6 VARCHAR(8000)
        ,@P7 VARCHAR(8000)
        ,@P8 INT
        ,@P9 VARCHAR(8000)


Set @P0 = '1blabla'
Set @P1 ='20190315'
Set @P2 ='20190315'
Set @P3 ='20190315'
Set @P5 ='20190315'
Set @P6 ='20190315'
Set @P7 ='20190315'

SET @P9 = '0bla'
Set @P4 =1
Set @P8 =1
SELECT *
FROM table1 Where
(
 Col18 IS NOT NULL
        AND Col75 &lt;&gt; @P0
           AND DATEDIFF(dd, Col146, CAST(SUBSTRING(@P1, 1, 4) + '-' + SUBSTRING(@P2, 5, 2) + '-' + SUBSTRING(@P3, 7, 2) + 'T00:00:00.000' AS DATETIME)) &lt;= @P4
        AND DATEDIFF(dd, Col146, CAST(SUBSTRING(@P5, 1, 4) + '-' + SUBSTRING(@P6, 5, 2) + '-' + SUBSTRING(@P7, 7, 2) + 'T00:00:00.000' AS DATETIME)) &gt;= @P8

     )
    AND Col39 = @P9
ORDER BY Col18 ASC
    ,Col31 DESC
    ,Col30 ASC;


To get a pretty seek with no sort or other operators (And a pesky residual predicate.)



Your result could look more like this:



Conclusion

Based on these tests, which may very well be 100% different for you, this is the index that I would initially go for:

CREATE INDEX IX_Table1_Col39_Col18_Col31_Col30
ON Table1(Col39 ASC  ,Col18 ASC,Col31 DESC, Col30 ASC)
INCLUDE(  Col146,Col75)
WHERE Col18  IS NOT NULL;


DDL + DML Used in this example

        SET NOCOUNT ON;
        DECLARE @i int = 0
        WHILE @i &lt; 100
        BEGIN
        INSERT INTO Table1(Col39,   Col75,Col146,Col18,Col31,Col30)
        VALUES(cast(@i as varchar(3))+'bla',
               cast(@i as varchar(3))+'blabla',
               DATEADD(DD,-@i,GETDATE()),
               cast(@i as varchar(3))+'blablabla',
               cast(@i as varchar(3))+'blablablabla',
               cast(@i as varchar(3))+'blablablablabla');
        SET @i += 1;
        END
        SET NOCOUNT OFF ;
        INSERT INTO Table1
        SELECT * From Table1;
        GO 7
        Beginning execution loop

   (6500 rows)

    GO