According to Wikipedia:
A month prior to the premiere of Star Trek, Desilu held a screening for NBC executives to help decide which episode to broadcast first, and several stories were considered. Executives were concerned that "Mudd's Women", one potential choice, would have reviewers discussing "space hookers"; they felt another possibility, "Where No Man Has Gone Before", contained too much exposition—even though it was filmed as a second pilot. The final choice was between "The Man Trap" and "The Naked Time". Justman felt that "The Naked Time" would make it easier for viewers to understand the characters, but later agreed with NBC's decision to show "The Man Trap" first. In the book Inside Star Trek: The Real Story, he suggests that it was "scarier and more exploitable than the others".
"The Man Trap" was the sixth episode produced. Although Rodenberry initially disagreed with NBC's decision, he and producer Herbert Franklin Solow came to believe it was the correct choice. Shatner also disagreed with the network, feeling that "The Man Trap" was the worst episode out of those available. The episode was the first episode of Star Trek broadcast in the United States, on NBC on September 8, 1966.
 = Shatner, William; Kreski, Chris (1993). Star Trek Memories. New York: HarperCollinsPublishers. ISBN 978-0-06-017734-8.
 = Solow, Herbert F.; Justman, Robert H. (1996). Inside Star Trek: The Real Story. New York: Pocket Books. ISBN 978-0-671-89628-7.
As for the other being out of order, this is not unusual, and is often the result of executives changing things in an effort to boost a show's ratings. This has become a TV Trope. This has happened for multiple shows (notably, Firefly), and can happen in any genre.
This is sometimes deliberate - the order in which episodes are filmed can be different to broadcast, usually for budget or other reasons. A good example of this is Star Trek: The Next Generation. The episode "Skin of Evil" in which Tasha Yar is killed, was filmed before the preceding episode, Symbiosis. As such, at the very end of Symbiosis, you can see Denise Crosby wave goodbye to the camera.
I'd suggest reading the TV Tropes link for a full list of reasons, as they are somewhat varied.