According to the view of the RAMBAN, your question is an excellent one. The Ramban (Bereishis 1:29) asserts that the only Heter for Noach to eat meat was that he saved them from the Mabul. As such, there would seem to be no reason to permit eating fish. (We cannot answer that Adam ha'Rishon was permitted to eat fish, but not other animals, because the Gemara in Sanhedrin (59b) states clearly that fish were also prohibited to him.)

The PARDES YOSEF asks a similar question to yours (Parshas Noach, 9:4). I then found that the KLI CHEMDAH (Parshas Bereishis, #3) asks your question. It must be that fish were made subordinate to all other animals, so that once man was permitted to eat the other animals, he was also permitted to eat fish.

(The MARGOLIOS HA'YAM (Sanhedrin 59:18) cites from the SEFER OLAM BARUR in the name of the ARIZAL that meat was forbidden to Adam ha'Rishon because the animals were perfect from their creation and they did not require a "Birur" (a special rectification) through being eaten by man. However, Adam ha'Rishon blemished the animals when he made them sin by feeding to them the forbidden fruit. Until the Mabul, though, the animals still did not need a spiritual rectification, since Adam ha'Rishon brought from them a Korban and through that their blemish was corrected, but at the time of the Mabul the animals sinned again (by being influenced by the morally corrupt ways of man), and therefore Noach and his descendants were permitted to eat the flesh of animals, in order to provide them with a spiritual rectification.

According to this, it could be that since fish were blemished by the sin of Adam ha'Rishon and their blemish was not corrected by the offering of a Korban (since one cannot bring a Korban from fish), therefore they became permitted to be eaten immediately after the sin, in order to provide them with a spiritual rectification, and they never again became Asur to man.)

Mordecai Kornfeld