Here's my two koku on this interesting character:
Regarding Okehazama, it was Nobunaga's recognition of the strategic opportunity and immediate action that demonstrated his prowess, not so much the tactical execution of the battle. He did not hesitate despite overwhelming odds, had the benefit of surprise and covering weather, and his men fought knowing that the fate of the clan was at stake. Yes, there was "luck," and the Imagawa were unprepared. But part of being a good commander is knowing when to act and not hesitating to engage in tatami-cushion analyses.
Another example of his ability to recognize strategic opportunity was the way he made use of the Christian missionaries and what they had to offer from the West. His use of firearms is well known so I won't go into that any deeper.
My understanding is that the Oda were poor in comparison to the other clans of the time. Other more established clans disdained the Oda, thinking Nobunaga a "small-time country daimyo." Hence I think his incredibly bold and audacious exploits might have seemed twice as big in the eyes of the people and his opponents. Perceptions <--> expectations, etc.
Nobunaga knew how to make use of established symbolic power, and fear. By firing Mount Hiei he sent a very clear message that there was little he wouldn't do against those who opposed his bid to unite and control the nation. leading up to the Mount Hiei incident, Nobunaga shrewdly secured the favor of the Emperor by manipulating the office of the otherwise ineffective Ashikaga Shogun.
Tokugawa Ieyasu, a respected daimyo of a granted, small clan, had deep respect for Nobunaga and allied with him for a very long time. This suggests much in the nature of Nobunaga's character.
Being a great leader is much, much more that just being a great battlefield commander. Proponents of Nobunaga have written that he had the fate of the nation at heart. He made excellent use of available resources, which other daimyos didn't recognize as quickly, and was willing to do whatever it took to achieve his goals. Total War, indeed.
Bookmarks