Optimization for branched WHERE
An execution plan was not included, but the typical issue with queries like this (sorting aside) is the optimizer choosing a nested loops anti semi join without a good supporting index. It can also be a rogue top (1), or a poorly-performing transformation to a semi-join with nested start-up filters and an anti-semi join.
Regardless, there are two usual workarounds:

Rewrite the OR manually as a UNION (or, if guaranteed disjoint, as a UNION ALL).
Rewrite the NOT EXISTS as a left join filtering the preserved side for NULL.

The following incorporates both:
DECLARE @thisTable table
(
    id integer PRIMARY KEY,
    refid integer NULL,
    refbool bit NOT NULL,
    col varchar(10) NOT NULL
);

INSERT @thisTable
    (id, refid, refbool, col)
VALUES
    (1, NULL, 0, 'val'),
    (2, NULL, 0, 'val'),
    (3, NULL, 0, 'val'),
    (4,  2  , 1, 'val'),
    (5, NULL, 0, 'val'),
    (6,  1  , 1, 'val');

SELECT
    U.id
FROM 
(
    -- T.refbool = 1
    SELECT T.id 
    FROM @thisTable AS T
    WHERE 
        T.col = 'val'
        AND T.refbool = 1

    -- Or (disjoint)
    UNION ALL

    -- T.refbool = 0 and not exists
    SELECT T.id 
    FROM @thisTable AS T
    LEFT JOIN @thisTable AS T2
        ON T2.refid = T.id
    WHERE 
        T.col = 'val'
        AND T.refbool = 0
        AND T2.id IS NULL
) AS U
ORDER BY 
    CHECKSUM(NEWID());

db&lt;&gt;fiddle online demo
For more alternatives on random ordering see the existing Q &amp; A:

What is the best way to get a random ordering?.

Don't just try the top answer.