Yeah most of the monstrous cohorts are available at levels where they are most often useless. For some, it is because of powerful SLA (constant True Seeing for Erynie). For others, you can't just understand why they have such a high cohort level (bralani 11th level ? So a 6-HD outsider in a 13th level party ??).
I think the best way to house rule this would be to use CR or HD (the greater of the 2) of the creature to determine the cohort level. But the problem with powerful SLAs will remain and the DM will have to adjust things ...
I did some analysis a while back since I wondered the same question. Generally, it's a combination of factors, including high stats (when a creature has high stats around 20 for everything, it would make quite a PC), SLAs, and other things. I tried to mathematize it in this thread:
http://paizo.com/threads/rzs2qbrt?Monster-cohorts-Level-scaling#1
Basically, if you chose a monstrous cohort, you do it for the flavor. THe power just aint there. But it's thematically interesting. Be careful about houseruling it to HD or CR, the designers did a fairly good job of "boosting" the level requirement based on powers/abilities. Though I will admit certain cases seem arbitrary.
CR indicates roughly how much of a threat a creature is to a party. CR is a poor indicator of utility as a cohort. Compare a unicorn's CR to its useful spell-like abilities.