I just tested the oldest firmware available in the Arch Linux Archive, namely
linux-firmware 20130725-1, and the crashes don't happen. This is with current
Arch, not a single package is old and all packages are up-to-date according to
the repos.

I'm hitting 10 to 30 FPS in-game, but at least the crashes don't happen which
IMO is a very good sign of where the problem might be.

I'll report the firmware problem to AMD.

In the mean time, does anyone know how I can try running the firmware from
Catalyst?

@Marek, where is the best place to report this?