Hmm, well the only version of NG I have played is Ninja Gaiden Sigma, and I played the original Devil May Cry but can hardly remember it, as well as now DMC4.
So in a comparison of NGS and DMC4 i would say NGS probably just edges it. I love both because the extreme levels of difficulty make for a very high level of satisfaction when you beat the tougher difficulties (just making my way through DMD mode now, it's great when each level is beaten). The main points are that there are greater differences in the main game when you play through Hard, Very Hard and Master Ninja in NGS than when you go through Son of Sparda, Hell or Hell and Dante Must Die in DMC4: i.e. New bosses and new varieties of enemies. The other main point is that I think Mission Mode in NGS is better than Bloody Palace in DMC4, although that may be just because BP seems the harder of the two and when (if) I get a decent way through it I may change my mind.
Some smaller points include Ryu having more weapons and therefore more moves than Nero and Dante combined, and also the fiend challenges dotted throughout the game (which also change with each difficulty) are a great addition. A trivial point is that less people play NGS so if you beat VH or MN you will be part of a much more exclusive club lol, when I beat Master Ninja at the end of last summer I was one of only 165, not including those who didn't upload a score.
That must sound like I much prefer NGS, but DMC4 has infinitely better cutscenes (the voice acting is hilarious and the action is just amazing) and also Nero's Exceed System provides an almost limitless possibility of improvement of your scores.
Oh and in my opinion you should definitely get NGS before NGII.