The alphabetical pagination part of your question is easiest to explain so I shall start with that.
You just need to change your $query to order the results by whichever field you choose.
So instead of:
$query = mysql_query("SELECT * from directory limit $offset,$limit", $con);
Use something like:
$query = mysql_query("SELECT * from directory ORDER BY fname limit $offset,$limit", $con);
So if you want to let the visitor choose what it is ordered by you will need to pass their selection through the url then retrieve it at the start of your script.
Something like:
if(isset($_REQUEST['order_by'])) {
$order_by = $_REQUEST['order_by'];
}
else {
$order_by = $_REQUEST['fname']; // default
}
Then change your query to:
$query = mysql_query("SELECT * from directory ORDER BY $order_by limit $offset,$limit", $con);
The displaying the results in two columns just needs a little bit of manipulation.
So when you are doing your while loop just keep track of how many you have displayed.
An example using tables for the layout because it is easier for you to see my point:
echo '<table>'; // start the table
$count = 0; //start a counter
while ($result=mysql_fetch_array($query)){ // start your loop
if($count == 0) {
echo '<tr><td>'.$result['fname'].'</td>';
// because $count = 0 we are doing the left hand side of the table
$count = 1; //increase the count
}
elseif($count == 1) {
// because $count = 1 we are doing the right hand side of the table
echo '<td>' . $result['fname'] . '</td></tr>';
$count = 0; //reset the count to 0
}
} //finish the while loop
echo '</table>'; // finish the table
The above is just an example to get you started, you can of course use css for your layouts.
Hopefully you can expand upon that to fit it in with your results / layout.