Update on my voyage into anime:
Cowboy Bebop is still great.
Robotech is so 80s it hurts. (There I watched it @Gnomeslice :P )
Trinity Blood is an interesting setting but can get pretty dark at times.
Trigun has given me faith in Japanese westerns (and that cat is great).
Outlaw Star seems like it will be interesting, though it gets weird at times.
Steamboy is proving hard to source. :(
As an aside, I can see why some people complain about what they see as the casual objectification of women in anime and such. :/ *attempts to duck controversy*