Time4Tea: I've watched the first 2 episodes of Cowboy Bebop so far and have to say I am thoroughly unimpressed. Episode 2: so another random, throwaway villain steals someone's dog and the two bounty hunter dudes (that I'm so emotionally uninvested in, I can't even remember their names) have to chase all over town to track it down. So far it seems quite formulaic and predictable, with very little character development. It's got absolutely nothing on Stein's Gate, imo.
I'll freely admit of all middle aged anime it's most hit and miss with people. Can't speak for comparison to Stein's Gate, they do not have much touching ground, not like the former and the titles I mentioned in the previous post, not even like latter and, say, Serial Experiments Lain, Erased, Darker than Black and Noein.
Time4Tea: Lately, I've been watching Record of Lodoss War, which I've been enjoying quite a bit. It's old, but seems well-made and fun. Also quite unpredictable, with some interesting twists and turns. Good show.
Check Legend of Crystania and Rune Soldier from the same setting. Watch Twelve Kingdoms and Wizardy after if you haven't already, they're also great fantasy classics. Or .hack//Sign, for fantasy adventure that takes place inside a MMORPG. One of the best soundtracks in the anime by my reckoning, too.