What a coincidence! I'm planning a planar binding in my campaign (my mage is calling a hound archon to serve as a bodyguardl; hound archons are great 'cuz they are reasonably tough but have a CHA of 12 so are easy to push around).
I made sure to check with my DM to make sure he's letting it work as it should; some DMs treat it as they do wish, i.e. a way to screw with PCs, which is flat out wrong. After all, you are casting a high level spell, along with magic circle and probably dimensional anchor. It should be at least as useful as any other high level spell, given that it requires a fair amount of resources and time. The DM shouldn't treat every outsider like it's some sort of legal genious with the ability to slip out of contracts.
Notice that you can't get a penalty in your bargaining, only a bonus. In my case of calling a hound archon, I explained that I should get a bonus since we are fighting against an evil cult of fallen angels; I don't know what bonus my DM gave for this, but if I were DMing this I'd actually give it the maximum (+6), since this sounds like something the archon would do on its own anyways.
Creatures I think are good to bind, because of usefullness yet low charisma scores (this is only for lesser planar binding... my guy is only a 10th level caster):
Hound Archons, especially if you're routing out some evildoers as I mentioned above. Plus they can turn into dogs, so you can bring 'em around town without much notice.
Bearded Devil, great if you are just killing things and taking their stuff. Why would an devil object to killing?
Howlers: Big, tough, and DUMB.
Nightmares. Cha of 12. And if it dies in your service you can just animate it as a skeleton and have a flying skeletal horse (since skeletons retain any magical flight)
Elementals, as others have mentioned. But right now my mage can only call medium elementals, and they're kind of wimpy.