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.
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)SQL In The Wild
: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter
We stand on the bridge and no one may pass