I'd like to see the Battle music randomized. Fifty percent chance for each theme. I think the idea of having one for each region is good, too.
By the way, Ice Penguin, a few more details about your music document. I think you may have some offsets that are, well, offset from the ones expected. I know that you use ROM offsets and not "real" ones. In section 4, it reads: "Starting at 0x1A00A, count $55 bytes ahead to reach 0x1A070." But, 0x1A00A + 0x55 = 0x1A05F. You are off by one byte. This makes the data entry more like:
18 42 A2 0D 09 15
The first byte is the Note Lengths offset. It's a multiple of 8, and is an offset into the table at 0x1914D (+0x10) :
1914D: Table for Music Note Lengths ? (6 * 8 = 30 bytes)
04 0C 08 10 18 20 05 06 ?
04 0F 09 12 1B 24 06 06 Battle
05 0F 0A 14 1E 28 07 06 Boss
06 12 0C 18 24 30 08 10 Overworld, Palace, Item
07 15 0E 1C 2A 38 13 12 Town, House
07 15 0E 1C 2A 38 09 0A ?
For any given song, you basically have 8 choices of note lengths. The bytes that represent the actual notes of the songs refer to these length values.
Randomized battle theme would be really neat. I think that could be easily achievable if we used the frame counter. Since it's always being incremented, a check could be done to determine which song is played. Though there probably is a better way...
Thanks for the feedback on the music document! It could definitely use improvement, so any advice is really appreciated. Yeah, I have a bad habit of using file addresses instead of real addresses. I understand it's important to use NES address when writing code, or sharing snippets of ASM code. I just like using file address when giving directions to a location. I'm sure as I learn more, and get better at ASM my view on that will change.

About your comment on section 4 of the document, from my understanding of how optomon explained it, he does say to count from 0x1A00A, but I always counted from 0x1A00B. I wasn't sure how to go about explaining this part, so I stuck with what optomon said since he knows better than I do.
The Note Length offset you mentioned, I'm pretty sure it's supposed to be the last byte in the phrase structure. That's how it was in the FDS version, and even when porting the battle theme over, it used that same 6 byte structure between the two versions. The original code from the FDS version was way too fast, so I used this byte to slow it down. I'm not sure what to think about optomon saying 0x1A00A, to be honest, but I'm confident it's the last byte.
Edit:I looked at that specific line you quoted from the document:
"Starting at 0x1A00A, count $55 bytes ahead to reach 0x1A070." I made a mistake. It should be 0x1A060! That's the start of the battle theme phrase structure. 42 A2 0D 09 15 08
I didn't experiment too much with the actual notation of the music, since composing music, or anything related to that, really confuses me. Does the table you referenced act as sort of a "global" tempo for any phrase in the song? I don't quite understand the connection between the Note Length byte and how the table affects note length. Also, the table sections being labeled as "?, Battle, Boss, etc." how are those related exactly?
Alternatively (just throwing it out there) you could have different songs for the easy and hard enemies. The FDS battle theme def sounds like a theme for harder enemies haha
This would be really neat, too!