We have a waiting list for games, which is nice. How about a "waiting list" for friends? A notify button which can be pressed. This will cause the selected friend(s) to be added to a notification list.

If a friend logs in, it tells you this happened. Right now, it'll either notify you if anybody on your list logs in or it won't notify you at all.