As a guy who made Newhart Quebec's theme, I don't really have a problem with using the orchestra. But I like the idea of giving Udan Mas to Mataram. I'll just use the orchestra's Jali Jali for Majahpit's peace and kul's suggestion for war.
Regarding Medang:
I've made a decision to dumb down the stats, but it should still be interesting to play.
UA: Monumental Age - Religious buildings and wonders generate
Great Engineer points in the Capital.
UU: Rakryan Kanuruhan (Great Engineer) - Can build Holy Sites, when Stationed in a city, earn 2
Production and 1
Faith per 2
Citizens.
UI: Candi - Unlocked at Construction. Can only be built on Flatlands or Fresh Water. Has the same yields as a Farm (That increase at the same rate) and 1 Production. Also generates Faith per era of existence.
Still synergizes quite well IMO, but puts more importance on the Unit and Improvement.
Also for the Candi graphics, since the almighty Wikipedia says that Borobudur is a candi, I'll be using it's graphics from the wonder tile pack.
Signing off on that civ I'll leave a little teaser for the music, Two Steps from Hell.
Kediri
UA: Spice Routes - The First 3 coastal cities spawn resources unique to Kediri. Trade route range increased in the capital per each trade route slot.
UU: Rakawi (Great Writer) - Creates Great Works of Writing that yeield 2 Gold
UB: Pentaran (Temple) - +2 Gold per religion.
The Building is tentative, but I'd like to keep the effects in some way. Obviously this is Gold Gold and more Gold. But I think it's nice focus.
Mataram:
UA: Kabupaten - Resistance time reduced by 50%. +2 Happiness upon conquering a city.
UU: Kavaleri (Lancer) - No defense penalty or city attack penalty. Starts with 15 XP
UB: Lumbung Padi (Barrack) - Units trained in this city heal faster in enemy territory
I like the lump sum of happiness better. It seems more active to me, which is perfect for a military civ.
Majapahit: Palapa Oath - Units gain a combat bonus for each city state you can demand tribute from or are at war with.
UU: Kris Swordsman - Same
UB: Wayang (Amphitheater) - 5% Culture in this city, 10% if the Great Work slot is filled.
Not as synergistic as the others but still is better than Firaxis's version.