Punk: Flogging Molly (the only punk band I listen to) Irish punk. Very fun and very cool.
Rock: Dream Theater. Progressive Rock, very technical, simply amazing. Check out "The Glass Prison," "Fatal Tragedy," "Home," "A Mind Beside Itself." Check out Blind Guardian as well. They're a German Metal band, but not very heavy, and tend to sing about LOTR a lot. Listen to "Lord of the Rings," "Noldor," "Excalibur." And since you said clasic rock, try Rush if you haven't heard them yet. Especially "Red Barchetta," "Spirit of Radio," "Time Stand Still."
Classical: Stravinsky. Just check out some of his stuff. He's pretty majestic sounding. Also try Dvorak's New World Symphony. I also really like Handel's "Arrival of the Queen of Sheba." Good choice with Holst, BTW. Mars is the best 🙂 Death metal band Nile did a song based on that piece, entitled "Ramses Bringer of War." It's probably far too heavy for your tastes, but it's an awesome song and you can definitely hear Holst's parts in it.