IMO, AV is the most useful interface in general, since it will work with anything. One reason to go with BT would be to avoid damaging the AV ports by having to move the Pandora around to control the media playback.
But I think that AV input is something to start with in picking a receiver, then you can figure out what other elements you want (iPod control, USB, BT).
It does seem kind of silly to have to buy a CD player if you don't want it, though. You may as well get a touchscreen / GPS receiver unit (except of course for the cost).
Car USB adaptors are far superior to the 7805 solution, as they're pretty much all switchmode devices (use less power, and get less hot). Additionally, designing a car power supply is trickier than you expect, because the '12v' supply is quite noisy - *especially* during ignition. Therefore proper smoothing is an important consideration.
I tend to have my usb adaptor unplugged when I turn on the ignition, just to make sure - although I've forgotten occasionally with no ill effects.
I did hooked up a little 7805 converter I made a few years ago to an oscilloscope inside a car and the max ripple was around 100 mV IIRC or so during ignition with some load. Of course YMMV.. but I was quite happy with that at that time.
Not 100% sure anymore but I think i did put a few little cap's more around it then the thing i linked.