VBR mp3.
I always encode with a 320 top and a 128 bottom. It works VERY well with a LAME based encoder. I don't like AAC because it's tied to iTunes and iPod and that's it. I've got 2 DVD player, 2 car stereos, a small USB mp3 player and every computer in the world (within reason for performance metrics) that can play mp3s.
I have seen so many bad outcomes from vendor lock-in, like the poor insurance processing company that had all of their print processing running on Interactive Unix (owned at different times by Microsoft, SCO and Sun) had been written by one guy who had passed away and they needed to upgrade some hardware and make some printing changes.
Closed formats (like AAC) are just plain bad. Even Microsoft is starting to open up their standards (XML based office format). The propietary game is what keeps Macs firmly in the < 3% of computers in the market.