SQL Server query performance on large datasets

Greetings,

I have an employee table in my SQL Server 2008 R2 database which contains more than 10 million records.
I need to display this data in a web application in addition to supporting functionalities like sorting, paging and filtering.
Moreover, I have separate forms for managing other CRUD operations like insert, update and delete.
Till now, I have managed to achieve a high performance by loading only chunks of data from the server (10 records per page).
I did face some performance issues in sorting but this was solved by creating non clustered indexes on columns I want to use for sorting whether ascending or descending. Also insert, update and delete operations are performing quite impressive with regards to the big number of records in this table.

However, still the big challenge is with tweaking and optimizing the performance of the filtering functionality. I just can't find the right answer for this. I tried several options like creating full text search indexes on fields that I want to filter on. I also tried to write the sql queries in many different ways with no obvious improvement. All other functionalities are taking less than one second to execute while the filter is ranging between 5 second to timeout based on the number of records returned from a search.

My web application load chunks of data based on two server requests. First request will get the number of records based on a search or filter criteria (This is required for pagination) and the second request will actually get only 10 records of the total result "Top 10" based on which page the grid stands.

Below is the script to create the employee table:

CREATE TABLE [dbo].[Employee](
[Id] [int] IDENTITY(1,1) NOT NULL,
[BadgeNumber] nvarchar NULL,
[FirstName] nvarchar NULL,
[LastName] nvarchar NULL,
[ProjectCode] nvarchar NULL,
[IsActive] [bit] NULL,
[SocialSecurityNumber] nvarchar NULL,
[IsMarried] [bit] NULL,
[BirthDate] [datetime] NULL,
[IsEngaged] [bit] NULL,
[IsTerminated] [bit] NULL,
[TerminationDate] [datetime] NULL,
[PassportNumber] nvarchar NULL,
[BankAccountNumber] nvarchar NULL,
[JobTitle] nvarchar NULL,
[Religion] nvarchar NULL,
[CreationDate] [datetime] NULL,
[ModificationDate] [datetime] NULL,
[PassportExpiryDate] [datetime] NULL,
[ResidenceExpiryDate] [datetime] NULL,
[Crew_Id] [int] NOT NULL,
CONSTRAINT [PK_Employee] PRIMARY KEY CLUSTERED
(
[Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

ALTER TABLE [dbo].[Employee] WITH CHECK ADD CONSTRAINT [FK_Employee_Crew] FOREIGN KEY([Crew_Id])
REFERENCES [dbo].[Crew] ([Id])
GO

Also this is a sample of queries being run on the sql server for the retrieval of data (Note that I tried all possibilities "like, contains and freetext"):

Count Query:

exec sp_executesql N'select convert(bigint, count(employee.Id)) as Count from employee where 1 = 1 and freetext(employee.projectcode, @projectcode)',N'@projectcode nvarchar(7)',@projectcode=N'"rmp"'

Select Query:

exec sp_executesql N'select top 10 * from ( select (ROW_NUMBER() over (order by badgenumber asc)) as rowNumber, employee.* from employee where 1 = 1 and freetext(employee.projectcode, @projectcode) ) as result where result.rowNumber > (0) and result.rowNumber <= (10) order by badgenumber asc',N'@projectcode nvarchar(7)',@projectcode=N'"rmp"'

Thanks in advance.

Mohammed