It feels like everyone keeps repeating the same dialog tree that 'but thou must store their contacts list' and I don't see why.

Solution? Store your contacts list on your device. Back it up with your offline chat backups (android does external chat backups now, IOS should be enabled plus give em icloud backups to boot).

with a new signal app on a new phone, you restore your chat backups and poof your contacts list gets loaded back. your new signal instance reconnects with the other clients and poof, Signal's excuse for using phone numbers and storing your contacts list on their servers is demolished.

It seems so simple to me, but I feel like I'm failing to understand something about why this is so hard.