I switched to your suggested route of checking dates first and the rest in the object query.

The generated SQL is the following:

exec sp_executesql N'SELECT 
    [Extent1].[id] AS [id], 
    [Extent1].[start_time] AS [start_time], 
    [Extent1].[end_time] AS [end_time]
    FROM [dbo].[max4sale] AS [Extent1]
    WHERE ([Extent1].[start_time] >= @p__linq__0) 
AND ([Extent1].[start_time] <= @p__linq__1) AND ([Extent1].[id] <> @p__linq__2) 
AND ([Extent1].[type] = @p__linq__3) AND
(([Extent1].[department] = @p__linq__4) OR (([Extent1].[department] IS NULL) AND (@p__linq__4 IS NULL))) 
AND (([Extent1].[category] = @p__linq__5) OR (([Extent1].[category] IS NULL) AND (@p__linq__5 IS NULL)))',
N'@p__linq__0 datetime2(7),@p__linq__1 datetime2(7),@p__linq__2 int,@p__linq__3 tinyint,
@p__linq__4 varchar(8000),@p__linq__5 varchar(8000)',@p__linq__0='2015-07-31 08:00:00',
@p__linq__1='2015-08-30 20:59:00',@p__linq__2=0,@p__linq__3=6,@p__linq__4='TICKETS',
@p__linq__5='ADULT'

I don't understand why do we have these strange NULL checks. Department, Category and Item columns are defined as char(10) not NULL in the table. Similar queries do not produce these weird NULL checks.

Also, is there a way to define a string that will never be null in C# ?