For a long time I've felt that "fantasy" or "medieval" isn't really a genre of music, even though it is a genre of setting.
There is actual historical medieval music but generally that's never used in games or films depicting that time. There's examples where someone has developed a strong successful style while working mostly in games of one genre, like Nobuo Uematsu or Hitoshi Sakimoto, and their example gets imitated... I've looked at this question of what is fantasy/medieval music over and over again, and every time it breaks down; there isn't really a big coherence to it as a genre, in my opinion.
Neverthless, here's a few vague ideas that I think fit the trends a little bit:
- Late romantic classical music and orchestration. A string orchestra. In particular the work of Debussy (example) which had a very dominating influence on film music for a very long time, and Nobuo Uematsu makes many direct references to Debussy in his work.
- Modal scales and harmony. I think Greensleeves is basically the archetype for the "fantasy/medieval" melody and harmony. This helps set it apart from just being derived from classical music, and modal scales were prominent in that historical period. I don't think it's used in a historical way, but it is effective at cultivating a mood that's different from common practice major/minor stuff.
- Influence from various folk music, which includes modal scales, unusual dance rhythms, etc. and also things like instrumentation. Acoustic instruments, but especially ones that aren't the common modern version, wooden flute instead of metal, lute instead of guitar, a simple tambourine instead of a snare drum...
- Carl Orff's Carmina Burana is another huge touchstone for this genre, maybe even its most representative work. Very strongly medieval "themed" but not trying to be a historical performance by any means, it does have that kind of anti-classical, strange/folk instrumentation/rhythm, modal melodies, etc.
(...and the way my 3 main examples here, Orff, Debussy, Greensleeves are all also drastically different from each other is an indication of what I mean when I say I don't think it's really a coherent genre.)
The second part of the question is where to look on the NES for examples... well I'd actually suggest a different approach:
1. Study NES music, but
don't limit yourself to things in your target genre. Things like "piercing" orchestration, well... just listen to lots of stuff and when you hear good orchestration, learn how it worked and take those ideas. This isn't really a question of genre, most ideas like that can be taken and used in many places. Just listen to a variety of "good" NES music and learn from it all.
2. Set your target/goals outside the NES. Pick some music you think is appropriate and you like the sound of and try to render that on the NES. You will necessarily need to make changes, adapt it, compromise, come up with novel solutions to work around the compromises, etc. but I find that attempting things like this has very good results, and a much better chance of creating distinctively new music for the NES than I could by using other NES music as the primary example.
Something like Yuzo Koshiro's Streets of Rage soundtrack didn't come about from trying to imitate something that was already on the Genesis. There was a genre of music he thought was under-represented there, and he took from that and
applied it to the Genesis.