TSQL speedup partition by query
If you have a separate table Clients with the list of all 1000 client IDs, it may be faster to seek 500 times into 1M rows table instead of reading all 1M rows. This is another common variant to write a top-n-per-group query. The following question discussed it in great details: Retrieving n rows per group.

Also, use filtered index to match your query:

CREATE NONCLUSTERED INDEX [IX] ON [dbo].[entries]
(
    [client_id] ASC,
    [creation_date] ASC
)
INCLUDE 
(
    [status], 
    [uuid]
) 
WHERE (status &lt;&gt; 'DONE')


The query (assuming you have Clients table):

SELECT TOP(500)
    CA.*
FROM
    dbo.Clients
    CROSS APPLY
    (
        SELECT TOP(1)
            dbo.entries.*
        FROM
            dbo.entries
        WHERE
            dbo.entries.client_id = dbo.Clients.client_id
            AND dbo.entries.status &lt;&gt; 'DONE'
        ORDER BY dbo.entries.creation_date
    ) AS CA
;