Originally it was a bird; Firebird. But as there already existed a software product with that name, after some time it was changed. Probably fox was the next best animal to go with fire.
Before it was called Firebird, it was called Phoenix (I don't remember the related icons though) [1]. The name's also referenced in about:mozilla