I've recently been perusing various articles about the historical development of the Algonquian languages, and there are enough strange sound changes floating around in the family that I thought it would be a good idea to start a thread to collect out-of-the-ordinary sound changes.
Shawnee had an unconditional (so far as I can tell; cf. Miller, 1959,
An Outline of Shawnee Historical Phonology) change *s -> θ. (EDIT: H13 informs me over IRC that this isn't actually a weird change at all and happened in a few places in South-East Asia, but whatever, I'm leaving it here).
Arapaho has enough weird sound changes for an entire family. A rundown of the wackier stuff from Goddard 1974:
*o -> i, unconditionally.
*k disappeared unconditionally, leaving no trace, leaving a gap that was filled by an unconditional change *p -> k.
*s -> n word-initially.
*č -> θ, unconditionally.
*m split into either /w/ or /b/ depending on the surrounding vowels, leaving a single nasal /n/.
Blackfoot changed nasals to /ʔ/ before stops (with a couple of exceptions and caveats.)
Cheyenne inserted an epenthetic /h/ before stops between vowels: p t k -> hp ht hk / V_V.
(I can't find anything about Eastern Algonquian, but Eastern Algonquian is fairly conservative and most of the relevant papers are conference papers to which I don't have access. I'll probably add more later, but I need to go bake.