The iPhone has hardware decode support for MP3 and AAC (M4A), so you'll want to use one of those formats. In other words, if you play an MP3 or M4A on the device, it will use very little CPU. OGG used way too much CPU the last time I tried it. In my experience, AAC will compress better in general. But it depends a bit on what frequencies are present in the source audio. Unfortunately you'll probably need to just try a few settings until it sounds ok. You can import your wav files in iTunes and right-click to convert them to AAC. Try some of the built-in quality options and see of the files end up small enough. Then, if necessary, start tweaking things like bitrate and quality. A variable bitrate will result in a smaller file usually but it can be difficult to determine how much it will compress.
EDIT: When I was trying to play OGGs on the iPhone, it was via FMOD and it was a 1st gen device. So, things might have changed since then. Still, unless the rest of your app isn't really doing anything CPU intensive, you might as well not spend CPU cycles decoding audio if you don't have to since MP3 and AAC are essentially free.
EDIT2: Also, to clarify the whole M4A/AAC thing, M4A is an mpeg container file that can contain AAC-compressed audio. AAC is the official successor to MP3. According to wikipedia, a 1MB/minute AAC stream (by 128kbps constant rate compression) will give you hi-fi transparency (i.e. nobody can tell the difference between compressed and the original). I'm not sure how accurate that is, but it sounds about right.
EDIT3: Your quality degredataion going to M4A was due to starting with an MP3. Always start with an uncompressed format, like WAV. I believe AIFF is normally uncompressed, but I'm not sure if that's always true.
EDIT4: The AAC compresser that's in Logic 9 might do a better job than the one built into iTunes, but the process will probably be more complicated.