[lubic]

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?