OrderBy int slow for large table join
You should retype the various Name columns from nvarchar(max) to nvarchar([right size]). It's unlikely that names will be up to 2GB in length, and making them max sized prevents them being used as a key in an index. A good general rule of thumb is to avoid large object data types wherever possible.

You'll probably need to make that change to the EF code, but in T-SQL:

-- Guessing at 100 characters maximum
ALTER TABLE dbo.[Status]
ALTER COLUMN Name nvarchar(100) NOT NULL;

ALTER TABLE dbo.Colors
ALTER COLUMN Name nvarchar(100) NOT NULL;

ALTER TABLE dbo.Sizes
ALTER COLUMN Name nvarchar(100) NOT NULL;

ALTER TABLE dbo.Widgets
ALTER COLUMN Name nvarchar(100) NOT NULL;


I have also changed the column definition to NOT NULL there.

Anyway, given indexes:

CREATE NONCLUSTERED INDEX IX_dbo_Sizes__DiameterInches
ON dbo.Sizes (DiameterInches);

CREATE NONCLUSTERED INDEX IX_dbo_Widgets__SizeId_ColorCode_StatusId__Name
ON dbo.Widgets (SizeId, ColorCode, StatusId)
INCLUDE (Name);


...you should end up with a plan that avoids lookups and sorts, something like:



With the small number of rows in Status and Colors, it is probably not worth indexing their Name columns right now, but that could change over time. In any case, if the name columns should be unique, you should constrain them to be so using a unique constraint or unique nonclustered index, for example:

CREATE UNIQUE NONCLUSTERED INDEX UQ_dbo_Colors__Name
ON dbo.Colors (Name);

CREATE UNIQUE NONCLUSTERED INDEX UQ_dbo_Status__Name
ON dbo.[Status] (Name);

CREATE UNIQUE NONCLUSTERED INDEX UQ_dbo_Sizes__Name
ON dbo.Sizes (Name);

CREATE UNIQUE NONCLUSTERED INDEX UQ_dbo_Widgets__Name
ON dbo.Widgets (Name);


Second approach

With the same indexes, if you are able to change the SQL, you could also separate out the Color and Status lookups:

DECLARE 
    @StatusId integer,
    @ColorCode nvarchar(6);

SELECT @StatusId = ST.Id 
FROM dbo.[Status] AS ST 
WHERE ST.Name = N'Available';

SELECT @ColorCode = C.ColorCode 
FROM dbo.Colors AS C 
WHERE C.Name = N'Red';

SELECT TOP (1) 
    W.*
FROM dbo.Widgets AS W
JOIN dbo.Sizes AS S
    ON W.SizeId = S.Id
WHERE
    W.StatusId = @StatusId
    AND W.ColorCode = @ColorCode
ORDER BY
    S.DiameterInches;


This makes for a simpler set of operations that also happen to make life easier for the optimizer:



Note also that Unicode string literals should be prefixed with N for correct data typing.

Oh, and you should also patch your instance. It is currently SQL Server 2008 Service Pack 1 - Service Pack 4 has been available for some time now.