It's been said, but Babylon 5. Just a flat out great show. The visuals are dated, but it's still very watchable. The characters are what's going to keep you coming back, though. G'Kar and Na'Toth deserved to be in more episodes together. One rivalry you'll see in the first season is gonna have a such a GOOD fucking payoff later on down the line, it still remains one of the best scenes on TV for me.
And again, even though you ruled out Trek, DS9 warrants a watch as well. It's a slow burner in the early seasons, but it kicks into high gear later on. Also has excellent characters and interactions, as well as a wholly unforgettable episode that is too damn good. Visuals are better than B5's, so expect better ship battles.