Detta kan kanske fungera, eller inte
Dock helt otestat (då jag inte har tabeller och eller data) samt att det inte finns stöd för att EventGender kan vara tomt, så det måste läggas på lite mer logik för att få till det, om resten nu mot förmodan fungerar.
select * from
(
select u.UserID userID1, u2.UserID, userID2
from EventUsers eu
join Users u on u.UserID = eu.EventUserID
join EventUsers eu2 on eu2.EventUserID != eu.EventUserID
AND eu2.EventGender = u.UserGender AND eu2.EventCity = u.UserCity
join Users u2 on u2.UserID = eu2.EventUserID
AND u2.UserGender = eu.EventGender
AND u2.UserCity = eu.EventCity
order by RAND()
) group by userID1
Men som sagt, det är otestat och jag är långt i från säker på vilket (om något) resultat som kommer ut.
Men testa och se om det kanske är en väg framåt?