If you thought Champloo sounded interesting, you need to check out its predecessor Cowboy Bebop, too (it's by the same guy, not a real sequel). Both are somewhat episodic, but they do actually follow a linear plot most of the time.
Steins;Gate is a good one if you enjoy sci-fi and plenty of humor. If you try it, though, try to keep going until the 12th episode. I didn't, but most people say they don't really enjoy the first half that much. It's my favorite anime, though, so I highly recommend it.
Eden of the East is pretty short and is sure to grab your attention right away with its first episode (*wink* lol), but you'll have to watch the two films to reach the ending.
Since you said no to FMA and Yu Yu Hakusho, the only other one I can recommend that's similar to your list is Rurouni Kenshin. It's pretty good, and watch its OVA Trust and Betrayal, too.