Compression doesn't necessarily mean quality loss: There are lossless formats that provide reasonable compression, for example Microsoft's WMA format has a lossless variant, there's Apple Lossless, FLAC, even a lossless MP3, all can provide audio compression without any quality loss. Think of it as taking the raw media file and running it through ZIP. The compression consumes resources but doesn't degrade quality.
On the other hand, lossy shrinking of media files can be achieved without any compression: You can resample the media at a lower sample rate, less bits per sample, mono instead of stereo or surround, etc.
When you consider the issue of computational efficiency vs. quality there are actually many more parameters to take into consideration. For example, a codec used mainly for speech (e.g., in phones or voice chat) addresses a different dynamic range than that of a music codec, and therefore the efficiency vs. quality measurements are quite different.
So what is the perfect "middle-ground" as you call it? It is up to you to define. Most modern codecs can be calibrated to suit your target efficiency in terms of storage-CPU-quality ratios by controlling many aspects of the encoding. The AAC format even standardized a set of formal "profiles" that combine some perfect "middle ground", each perfect for a specific task.
All that said, looking for the "best" codec isn't just a matter of format. Most formats typically have several implementations, and as we know some programmers are good, some are even better...