Try different papers including: hot-pressed (smooth) watercolor paper, medium and cold-pressed (rough) watercolor paper, illustration or matt board (Bristol board or Museum board), as well as traditional favorites like Stonehenge. Consider how well the tooth holds the pencil, whether it takes many layers, and whether the texture is too pronounced for some effects.
Try working on a variety of paper colors, too - from crisp pure white to cream and grey, as well as colored paper and black.
Pencils companies are reluctant to share recipes, but most pencils are wax-based, with the best brands having a high percentage of pigment. Some feel dry, almost chalky, while others are oilier. Try a range of brands; many are available as loose stock, so you can try just a few colors. While reviews can be helpful, everyone works differently, so another person's favorite might be entirely unsuitable for your way of drawing.