I've done an NSG challenge before, and I thought it was really fun. I found that lot of farming for items is involved in the challenge. You can get armor with No Encounters ability later on (dropped from a ghost in the sunken cave), and this should make it easier to get around, esp. before you get the airship.

As Necronopticous said, the Aeons get stat boosts after every certain # of encounters.

You can also beef up your Aeons' stats using your various spheres once you get Aeon's Soul. Whenever you obtain Summoner's Soul later on (thru a sidequest you can do), you can teach your Aeons new magic abilities and skills using your various spheres and items.