I do not understand. Were you choosing words in a type what you hear exercise? I have never seen that before.
Myši is certainly wrong here. What you hear as the "i" is actually just a glottal stop that separates the š and the j. The audio is correct and there is no "i" there.
Myš is feminine. Myš, gen. myši as kost, gen. kosti.
Such a rule does not exist. There are several declination types for each gender:
Masculine: pán, hrad, muž, stroj, předseda, soudce
Feminine: žena, růže, píseň, kost
Neuter: město, moře, kuře, stavení
As you can see, there is no consonant/vowel ending rule. You have to remember the gender of each word (or the declination).
You're not crazy...! One of my textbooks notes that "Nouns ending in a consonant are VERY LIKELY to be masculine" and "Nouns ending in A are USUALLY feminine." IMO, statements like these are presented to the learner as clues as to gender, but definitely not as absolute rules. So they can be helpful... and they can also muddy the waters a bit, as I know from personal experience!