Eu teria uma tabela de links para amigos, ou qualquer outra coisa, com 2 colunas sendo ambas PK's e ambas FK's para a tabela User.

Ambas as colunas seriam o UID e você teria duas linhas por relacionamento de amigo (A,B e B,A). Contanto que ambas as colunas sejam PKs, ainda deve estar no formato normal (embora outros sejam livres para me corrigir sobre isso)

É uma consulta um pouco mais complexa, mas nada que não possa ser abstraído por um procedimento armazenado ou alguma lógica de negócios, e está no formato normal, o que geralmente é bom ter.