Your sample rate must be twice the maximum frequency of interest. This is the Nyquist–Shannon sampling theorem. If you want hi-fidelity audio, your maximum frequency is the limit of human hearing, about 20kHz. Human voice is less demanding: telephone networks work up to about 3400 Hz.
You will find that the AVR's ADC isn't terribly fast, and you don't have much resources to process the data. So probably, your hardware limitations will dictate the sample rate for you.
You probably don't need to worry about codecs. A codec encodes and decodes an audio stream. A common thing to do is compress the audio for more efficient storage or transmission, but it doesn't sound like you are doing either. There are codecs that encode and decode for reasons other than compression, but I can't think of any that would be relevant here. Your computing resources are very limited on the microcontroller anyway, and you won't have much time for encoding or decoding anyway.
It's hard to tell what you are asking because some things you say don't make sense. In the schematic you show, both outputs are clearly referenced to ground. Pin 5 produces the inverted signal and pin 8 the non-inverted, but both are referenced to ground. The DC offset of both will be close to half the supply voltage.
However, if the point of this block is to be a preamp, then the choice of this part makes no sense. You didn't supply a link to the datasheet so I don't know what a LM4871 is exactly, but from the schematic you show it appears to be a small power amp. You can see that the gain of each output is 1 referenced back to the input. The main job of this circuit seems to be to provide power gain (lower impedance output) as apposed to voltage gain, and to produce a differential signal to drive a small speaker with directly. This does actually give you a voltage gain of 2 accross the speaker relative to the input, but the main point is to be able to drive the speaker with ± the supply voltage. That is useful to put more power into the speaker from a low supply voltage.
If you want a preamp, make a preamp, and use parts intended for some voltage gain with good characteristics of noise, linearity, and distortion. This is not what the LM4871 is intended for, given the schematic you provided.