Human relations between users
You may want to recognize directional relationships (e.g. "is the mother of", "is the son of") or you may need to acknowledge that relationships are not bilateral insofar as the users don't grant each other exactly the same rights.  In that case you need to keep two records in users_relations for each relationship.  Otherwise, I would just capture each user linkage once.  

Union queries take about twice as long as single queries, but when these queries are built on fast operations like index seeks this isn't so bad.  In any case you'd be trading this off against twice as much storage, which mitigates the impact slightly.

I'd be much more concerned about the potential headaches of managing the redundant data (if it is indeed redundant).

You could pick a convention like lowest id_user first to make certain kinds of operations more predictable - such as updates and deletes.