If you're looking for a great flavor with pork tenderloin, it's going to come mostly from the rubs or marinades. Then cooking method will make a difference as well.
Try an Asian style marinade using soy sauce, ginger, garlic, chopped scallions, sesame oil and dry sherry or rice wine.