Você deve forçar o mecanismo de banco de dados a avaliar um novo valor para cada linha. Você pode fazer isso adicionando a cláusula where dummy na tabela externa como:
DECLARE @city TABLE(ID INT IDENTITY(1, 1), City VARCHAR(100))
INSERT INTO @city VALUES
('Dallas'),
('New York'),
('Washington'),
('Las Vegas')
DECLARE @random TABLE(ID INT IDENTITY(1, 1), City VARCHAR(100))
INSERT INTO @random VALUES
('Manchester'),
('London'),
('Oxford'),
('Liverpool')
SELECT * FROM @city c
CROSS APPLY(SELECT TOP 1 * FROM @random r WHERE c.ID = c.ID ORDER BY NEWID()) ca
se você remover
WHERE c.ID = c.ID você obterá o mesmo valor para todas as linhas. 
