Para o usuário final, a diferença é negligível, pois o browser (ou aplicação em geral) que fizer a requisição, vai normalizar o endereço em um tempo imperceptível.
Porém, se você considerar a facilidade de manutenção dentro do escopo "eficiência", tudo muda:
URLs absolutos tendem a ser uma dor de cabeça ao reaproveitar o markup para mudar o site de endereço ou replicar a estrutura em um site novo, e são impraticáveis se você atender mais de um URL com funcionamento diferente pelo mesmo script/página (no caso de a mesma aplicação atender a vários URLs) ou quiser atender tanto
http://
quantohttps://
.URLs relativos (sem a barra inicial que indica "relativo à raiz") têm sua vantagem em estruturas que podem ser reaproveitadas em níveis diferentes do site, mas são mais complicados de manter quando a estrutura referencia coisas que deveriam estar sempre no mesmo lugar (como ícones de um site).
URLs relativos à raiz tendem a ser melhores para coisas globais, e evitam muitos erros e perda de tempo nos casos mencionados no parágrafo acima, se referindo a arquivos de mídia e scripts de uso global do site.
O ideal na maior parte dos casos convencionais de site e aplicação web é um misto de relativo com relativo à raiz, sendo relativo à raiz para coisas globais, e relativo à pasta (sem barra inicial) para coisas que podem mudar de nível (como uma coleção de pastas e scripts de uma sub-aplicação ou funcionalidade isolada do site), seja na mesma aplicação, ou no reaproveitamento de código para outra aplicação.
Quando você vai dar um redirect enviando um header
Location: http://www.exemplo.com.br/
, deve usar sempre um caminho absoluto
Quando pretender usar URLs em CSS que possa ser incluído com @import
talvez seja interessante usar o caminho relativo à raíz, para não se perder ao tentar debugar folhas de estilo em níveis diferentes do site.