I haven't read all of the responses to this post. But IMO, Brazilian Jiu Jitsu is the only 'belt' you will truely earn. I'm going to get a lot of flack for this from other martial artists...but I don't really care. In Karate or TKD, most people just pay for their belt. Spend enough money, and enough time, do little work...and you can be a TKD or Shotokan Karate black belt. But, a legit blue belt would break the arm of a TKD or Karate black belt. I don't go looking for fights, but, the 2 street fights I've been in - both of them went to the ground. Ask most guys that have been in a fight, and they always end up hitting the ground. Learn BJJ and you'll easily neutralize a boxer, brawler, or TKD black belt.
Chose your martial art for what you want to use it for.
Pure self defense with real life fighting strategies - Krav Maga
Cardio, body sculping - Muay Thai Kickboxing
Ground fighting and all around conditioning - Brazilian Jiu Jitsu
I train in BJJ, Muay Thai, and submission grappling. If you chose BJJ, find a legit jits school. Gracie schools are always good. If you want to train Muay Thai, find a gym where the guys actually compete in fighting matches. Find people who are teachers and fighters. I personally wouldn't learn any martial art from someone who hasn't had physical application of it.
As far as finding a good Krav Maga school. Ask the instructors who they teach. If they teach local police and military, then I'd trust their training.