I previously posted the somewhat complicated history behind Leucadia's name. For the curious, the history of how Greenlight Capital got it's name is pretty simple. It was given by Einhorn's wife.
As he explains it in Fooling Some of the People All The Time:
"In early 1996 ... Cheryl named the firm, giving me the green light. When you leave a good job to go off on your own and don't expect to make money for a while, you name the firm whatever your wife says you should."