I read once a stellar idea to help get over the fear of starting to draw in a notebook (or an art project, or a new software project) is to just start scribbling and drawing. Intentionally starting with a mess makes it much easier to break the cycle of "This thing I'm doing isn't good enough yet for this".
One notebook brand my wife found, that I love very much, is minimalism art. I like the small, softcovers. They aren't too soft, and hold their shape really well. The paper quality is high.
I also just tried out the new "sidekick notepad" from Cortex. Very expensive (overpriced), but I was happy to support their work.