Hmmm...
Yea theoretically the Pandora should be able to handle just about anything that VLC media player can handle, but as others pointed out - the SDHC speed will probably be the true bottleneck for limiting just how high quality you can play back on the device without choppy playback.
And just for the sake of asking somewhat related questions... what's a more advanced codec? Xvid, Divx, or 3ivx? Or is it one of those "no wrong way to eat a reeces" type scenarios between those three (since I never noticed a big significant difference myself).