If you're optimizing sound (music, voice, effects, etc) for showing on the internet, or download. I can't seem to find a good audio compression that doesn't either cause clicking issues or sounds like you're listening through a tin can. And leaving it uncompressed makes the file size too large.

Any suggestions would be welcome :)

Daniel,
What are you encoding with? Procoder, Vegas, even Windows Media shouldn't be creating any sort of noise like you are describing.
Windows Media at 64kbps is very, very good. You can listen to several samples if you click the "All Things Vegas" in my signature, and click on the Free Files link.

You'll hear editable quality in a streaming or downloadable format.
Real and Windows Media, Ogg Vorbis, these are all outstanding compression formats.

I'm using an old secondhand version of Adobe Premiere with the Sorenson 3 codec for general video work, and I usually use an audio codec called QDesign Music, but it sounds really really tinny no matter what I do.

Any suggestions on video codecs would be handy too. I need compatability and quality while keeping filesize down.

[EDIT: I'm fairly new to this, but after entering a small film contest and one of the only complaints was the audio quality, I feel that I need to address this]

Windows media. Forget Qdesign, that sucked when it was released, let alone today...
And Windows Media is free.
Same goes for Windows Media for video.
If you want compatibility, it's tops. Even Macs can open up to Windows Media 9. Everything opens Windows Media 8.
Until you hit high bitrates, nothing compares to Windows 9.
Real Media is very close, but their player is found less and less due to their stupid installation "take over my machine" concept.

I've heard that Windows Media was NOT Mac compatible, but of course I may be wrong.

If nobody else posts to the contrary, I'll give it a whirl :)

http://www.microsoft.com/windows/windowsmedia/software/Macintosh/osx/default.aspx

You should try to get a cross upgrade deal with Sony to get Vegas. It works with wmv and wma very well, and has the best audio capabilities of any NLEs it can reasonably be compared with.

The best codec at low bit rates is probably AAC. It is an ISO standard, with software available on both Mac and PC. I can send you samples if you are interested.

The only problem is that current editing applications don't support it (yet), so you have to demux the WAV file and compress it separately. If you want an easy solution, there is Windows Media Audio...