As far as audio-only, MP3 is as good as AIR supports. If using a video container (MP4, M4V, F4V), AAC is available.
MP3 audio quality shouldn't be an issue, provided streaming at a higher bitrate is acceptable. A bitrate of 160kb/s or higher for stereo content, I expect would be indistinguishable from the original source for the majority of people. Indistinguishable quality loss at lower bitrates is feasible, depending on the content (mono, voice only, etc).
More advanced codecs like AAC (available in AIR within video containers) and Opus (not available in AIR sadly) don't necessarily sound better, because above a certain bitrate they're all indistinguishable from each other. Rather, they're able to maintain perceptible audio quality at lower bitrates.
So is the bitrate the issue?