The only bands on your list I’m familiar with are Blind Guardian and Nightwish.
But if you like those, check out:
Stream of Passion They’re in the process of recording their second cd after some lineup changes. The first cd was amazing, IMO, best female fronted band I’ve heard in years. I’d describe them as European Rock, not super heavy or thrashy. Their guitarist on the first album (Lori Linstruth) is amazing.
Ayreon Dutch musical genius who writes these elaborate sci-fi concept albums, plays most of the music himself, then gets singers he likes to do vocals. The list of guest vocalists is pretty impressive, and reads like a “who’s who” of European metal. Best album is Into the Electric Castle, which is one of my top 5 of all time. Albums are a mix of heavy, acoustic, folk, rock, electronic, etc. BTW Stream of Passion started as one of his side projects. You might also be interested in another of his side projects, Star One, which is a bit heavier than most of the Ayreon stuff, and has songs based on famous sci-fi movies (Star Wars, for instance).
Rhapsody (now Rhapsody of Fire) A mix of classical and Metal, somewhat similar to Blind Guardian, especially Nightfall in Middle Earth. A Bit more melodic and less thrashy than BG, although guitarist Luca Turilli can shred. The storyline is original and spans 5-6 albums, about a warrior fighting to save his lands from evil. If you really like Blind Guardian you need to check these guys out.
Dragonland Swedish Metal band similar to Blind Guardian and Rhapsody, but much faster. Original fantasy storyline involving elves, dwarves, and whatnot. Very fast and heavy.
Within Temptation If you like Nightwish, definitely give the Dutch band WT a listen. Sharon has an impressive voice, if not quite as operatic as Tarja from Nightwish. The Silent Force is one of my favorite all time albums, and I actually like them a little better than Nightwish. Plus they don’t have a fierce growly cookie monster guy like NW does, which is a plus IMO.
Just for something completely different:
The Black Heart Procession. Slow and spooky for the most part, these guys sound like they’re doing a soundtrack to a horror movie. If you really want to creep your friends out, start playing this for them late at night. Not gory or violent, just…creepy. Until I heard this band I never knew the piano could be a creepy instrument. The best albums are 2 and 3, IMO (the first 3 albums are numbered instead of named).
Colonel Jefferey Pumpernickel: A Concept Album Not sure how to describe this, other than it’s very good, and one of the flat-out weirdest albums I’ve ever heard. Steven Malkmus (probably tripping or something) came up with a bizarre idea for a concept album, and sent ideas for each song to a different indie rock band, with some general guidelines. Unfortunately the full site doesn’t seem to be up, just the front page, but the storyline is something about childhood allergies, hallucinations, great underwater fire battles, and a hooker mistaken for a nurse. Can be ordered from Off Records, which specializes in similarily bizarre stuff.
but here are some bands from my playlist that I think you’ll like if you haven’t heard them (some old, some new):