Most important : choice! This will also be the hardest to comply to since so many people have so many tastes.
Almost equally important : sound quality! It should sound at least as good as a normal radio or else I could just turn that thing on and I would have no need for Radio MX.
I can live with commercials, but not with pop-up ads. As Ynot has already stated : they bother me in my work and annoy the hell out of me.
I guess a fair price would be about $3/month. Keep in mind that this service is not really needed ; anyone with a radio can substitute for it, so it should really get itself noticed or be 'different than the others'

Then again, you're askin this to people who probably listen to their Mp3 collection for probably 99% of their listening time.