Some of my favorite Metal/Hard Rock/Progressive/Whatever you want to call it:
Isis (they had their name before the terrorists and are no longer together) - These guys draw a lot of the same influences as TOOL does. Lots of melody, lots of fun time signatures, great growling vocals. and some heavy riffs.
Electric Wizard - If Black Sabbath had a stoner metal baby, this is what it would sound like. I heard these guys on vinyl at 3Floyds in Munster, Indiana and immediately bought the album.
Godflesh - I really only dig their album Hymns, but it's a badass album.