The people who have used Kids Nite Out have liked them, as I recall from these boards. You might want to try a search for past messages on the family board for Kids Nite Out.
We decided to use Fairy Godmothers because of all the good reports on these boards, and since we've had such good experiences with them ourselves now, we see no reason to switch. As people have pointed out, Kids Nite Out is the Disney-sanctioned service, with training and the like. It's also more expensive than FGs. And with FGs, there are fewer sitters but they tend to have worked for FG for years, so we were comfortable with that.