Partitioning is unlikely to help at all.
Unless you can add some SARGable predicates (predicates where SQL can use indexes to reduce the rows it has to read), there's probably not much that can be done. LIKE with a leading wildcard requires SQL to read every row, so that query will read every row of the table.
Full text may or may not help. Try it out and see.
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability