I'd define "genius" by breaking down and analyzing the concept of "proficiency".
I like to think that for any skill, people are born with varying levels of ease in picking up the skill and/or developing it (nature). Extreme examples include people who feel like "I've done this before", which have some parallels with the awakening of Kekkei Genkai in the Naruto universe. From "baseline" level of ability, people can work to raise or lower their proficiency in proportion to how much effort they spend (nurture).
I would say that a "genius" is someone who was born with an extremely high level of baseline proficiency. Hence, with regards to your question, does a genius have to be smart, analytical or a fast learner? These three qualities differ slightly in character:
- Concerning the skill of intelligence, people who are born smart are geniuses, but people who became smart after studying/practicing very hard need not be.
- Concerning the skill of analyzing the battle situation, people who are born analytical are geniuses, but people who became analytical with decades of battle experience need not be.
- Fast learners "develop their skill abnormally quickly" so they can be all considered geniuses (very fast learners, that is).
According to my definition, Jinchuuriki and lineages of powerful Kekkei Genkai (such as the Sharingan or Rinnegan) automatically qualify as geniuses. Interestingly, in the real world we don't have that much of "inherited genius" to be unleashed, so this is unique to the Naruto universe. Thus, to answer your question, Naruto, Sasuke, Itachi and Nagato are indeed geniuses; from Morpheus's answer, Shikamaru is one too.
However, it is important to define the scope of one's genius; different types of genius cannot be compared.
- Shikamaru is a genius when it comes to "being smart" or "analyzing the battle situation".
- Byakugan users are sensor-type geniuses.
- Rock Lee is a proficient Taijustu user but is not a genius; he simply worked extremely hard to attain that level of skill.
- Naruto and other Jinchuuriki are geniuses in chakra-intensive (and thus powerful) techniques.
- Naruto is also a sage mode genius (being able to perfectly balance natural energy with his own chakra).
- Regarding JNat's comment to the question, Naruto's proficiency in many other skills (walking on trees comes to mind) came from extensive training due to his spirit of "never giving up", but he cannot be considered a genius for those.
- However, Naruto may be a genius at learning and picking up most skills quickly; coupled with his determination, that is a potent self-improvement skill in itself.