What you might want to do is go to a site like
Anime Academy and just read through some of the descriptions and reviews to see what appeals to you. And then maybe gather some names of ones you think sound neat and see what some PPTer's opinions are of them. That's usually what I do, is search for a title on AA to see what they think, and then do a little more research at some other sites. I'm lucky though. My local comic book store has the largest anime selection in the entire state of Indiana (or at least it did a few years ago, and given how much it's grown, I'm betting that's still the case), so I can pretty much rent anything before I go off and spend big bucks to actually buy it.
Unfortunately, I haven't seen Tenchi or Outlaw Star, so I really can't recommend something based on the fact that you liked them. However, I'm guessing someone that likes Tenchi might like Love Hina. Maybe? ^^;;