Favorite pencil: Rotring 500 0.5mm, with Pilot Neox 4B lead. I never much liked pencils before I found this lead. It's the softest I've found in 0.5mm, softer than most brands of 4B. It lets you write with very little pressure so it feels more like using a pen. The Rotring 500 has the same solid and reliable mechanism as the famous Rotring 600, but a plastic body so it's cheaper and lighter. But despite being a good pencil, I can't recommend it as strongly as the Lamy Safari because of one major flaw - it has no end cap. I reserve it for desktop use because the end pipe is completely unprotected and fragile.
I have no strong preferences for paper and IMO a good writing implement should work with any common paper.