Puedes usar "LIKE" .. pero con los "comodines" (wilcards) de tipo 'dato%' .. es decir .. el % al final indicaría "que empiece por" ...:
$sql = "SELECT id, nombre FROM tabla WHERE nombre LIKE '".$_GET['letra']."%' order by nombre desc";
y luego te haces los links hacia tu script pasando "letra":
Código PHP:
<a href="nose.php?letra=a">A</a>
etc...
Y si a esto también quieres "paginarlo" a su vez .. usa el "Paginator" de Jpinedo (usa el buscador del foro).
Un saludo,