Best way to show friends of a user in alphabetical order

On a social network I am working on in PHP/MySQL, I have a friends page, it will show all friends a user has, like most networks do. I have a friend table in MySQL, it only has a few fields. auto_ID, from_user_ID, to_friend_ID, date

I would like to make the friends page have a few different options for sorting the results,

1. By auto_ID which is basically in the order a friend was added. It is just an auto increment id

2. new friends by date, will use the date field

3. By friends name, will have a list in alphabetical order.

The alphabetical is where I need some advice. I will have a list of the alphabet A-Z, when a user clicks on K it will show all the user's name starting with K and so on. The trick is it needs to be fast so doing a JOIN on the user's table is not an option, even though most will argue it is fast, it is not the performance I want for this action. One idea I had is to add an extra field to my friendship table and store the first letter of the users name in it. User's can change there name at anytime so I would have to make sure this is updated on possible thousands of records, anytime a user changes there name.

Is there a better way to do this?