"That said... I doubt I would ever take the time to assign an alias to everyone I am following, so I am not sure how much use this would get in practice." That's why the client should make these entries at the time you are first following somebody. If I follow Dikaios1517 and you change your name tomorrow, I will have no idea who's that but I might remember who I did follow yesterday.

The client should be mindful of course. So I would like my client to show both pfps in some way. For example the old one on hover with a mark hinting at a change having happened. So when I hover the pfp, a second pfp would slide from under the current one, allowing me to pick one, after which the pfp would stop being marked until the user changes his pfp again.