My favorites include Vandread, Nadesico, Gatekeepers, Dual, Noir, fullmetal.panic!, RahXephon, and Witch Hunter Robin to name a few.
Some of those are only in fansubs right now, some are released in the US and some are licensed. If you want an idea of what Noir is about, I'd suggest watching my Noir AMV http://www.animemusicvideos.org/legacy/video.php?v=4551
it doesn't have any spoilers and I think it give a good representation of what makes the anime so cool without giving away too much. ^_^
AMVs are a great way to find anime to watch. "Believe" got me to watch Battle Athletes Victory (there's another good one - cheap too!) and Cauldwell's Engel video got me to watch Evangelion.
If you're looking for series' like CBBB and Trigun though, I'd suggest Outlaw Star. That's the 3rd anime in that trio of 3 that came out at the same time and had similar styles.