i've never heard of those examples you gave, but just taking a wild stab at what you might be looking for, i'd suggest trying Collective Soul circa 1994-2000 (their first five albums). my personal favorites being Dosage and Blender. be warned, much of their new stuff blows.
and though it may be harder than what you're looking for, i always recommend shinedown. they are hard rock, but not metal. they went a bit more "mainstream" with their current album.
You know, I found that I felt the
exact same about Collective Soul as you do... Back when I was an Embry student, some students would have their iTunes libraries linked over the hard-wired network. Someone had a lot of Collective Soul, and I gave it a listen as I really liked what I heard on the radio. Unfortunately, (as you said) much of the actual albums were hit-and-miss.
However (contrary to our mutual consensus), several bands seemed to pop up in rapid succession, and amongst them (Shinedown, Three Days Grace, etc.) seemed to share very similar attributes in sound. I'd agree that Shinedown is probably the best among the choices, but DEAR GOD...
Three Days Grace ****ing blows. They're probably one of the worst bands I've ever listened to on the radio, and I have no idea
why they got so much airplay.
...So yeah, don't listen to them.