I was going to come in here and post a huge list, but I’ve been beaten to virtually every band I was going to mention. So I’ll settle for seconding a few of these bands:
Opeth - Truly one of the greatest bands out there. I didn’t like the growling (“Cookie Monster” vocals) at first either. But once you’ve listened to the songs a few times while reading the lyrics, you’ll get to understand them and appreciate them a lot. If you still don’t like the growling, you might want to check out their latest CD, Damnation. Not heavy at all, but a masterful album, nonetheless. I’m sure some would disagree with me on that, though.
In Flames - The lead singer does quite a bit of screaming and growling also, but they are just so damn good! My favorite albums from these guys are Colony and Clayman.
Amorphis - These guys started out as a seriously dark Doom Metal band, and have…heh…morphed into something truly amazing. They released two albums with a guy who just growled, then for Elegy (one of the greatest metal albums EVER EVER EVER) they picked up a guy for clean vocals, and they took turns throughout the album. They do primarily clean vocals now. From the OP, I think you’d best like Tuonela, although I really like their latest called Far From the Sun.
Angel Dust - These guys are from Germany, and do straight up Power Metal. They kick so much ass live it’s impossible to describe. Albums to check out: Enlighten the Darkness, Bleed, Of Human Bondage.
Katatonia - I don’t really know a lot of their older stuff, but their last three albums (Discouraged Ones, Last Fair Deal Gone Down, and Viva Emptiness) are all great. Especially Viva Emptiness.
Lacuna Coil - My brother gave me a mix CD of this band and I had to go out and buy every album they’ve done. Absolutely brilliant. Unleashed Memories and Comalies are two CDs that have been in my rotation for over a year now. And the girl they have doing lead vocals is really sexy, too.
Nevermore - These guys are one of the first real metals bands I discovered a few years ago, and they remain one of my favorites. The Politics of Ecstacy and Dreaming Neon Black are still two of my favorites, although I really like Dead Heart, in a Dead World. Their newest one, Enemies of Reality, is an excellent workout CD, in that most of it just mindlessly heavy (not that there’s anything wrong with that).
Symphony X - I know you said you were already listening to these guys. I’d just like to say that their newest CD The Odyssey is absolutely amazing.
Vanishing Point - I just discovered these guys a few weeks ago when I got a copy of Tangled in Dream. I really like them. The lead singer sounds like Dan Swano, but I’m not sure. Check them out.
Wow, that went on a lot longer than I thought it would! Good to know that there’s a few other metalheads here on SDMB.