Viendo tu 1era solucion me di cuenta que se me olvido colocar el codigo que hace los enlaces para cada pagina,
Código PHP:
echo paginar($pag, $total, $tampag, "listar_socios.php?pag=");
por lo que leo de tu 1era alternativa deberia quedar algo asi??:
Código PHP:
echo paginar($pag, $total, $tampag, "listar_socios.php?pag=&ordenar");
la modificacion deberia ir entonces en el codigo que crea los enlaces de cada pagina.....