Cheap filler note paper is a source of difficulty when writing(ball pens will skip, dark inks will bleed, scratchy pencils and nibs will tear). The index cards work, but I would also go for the slightly more expensive paper brands one can find on JetPens. If you're going for a stationary experience, investing a little more in it goes a long way.
I like use a 5.5 x 8.5 or 9 x 12 Strathmore 300 Sketch tablet for notes. They are sturdy and the paper is quite good. They are a pain if you want to scan/copy them as the paper is either smaller or larger than standard letter size.
Yes I also use sketch pads with no lines (The grey spiral-bound ones sold by WHSmith in the UK). I don't understand the attraction of lines given that software is hard to describe without diagrams.