What size innertube for 35mm tires? (or: get innertubes on the big side or small side?)
Either will work.

Use what your prefer.  Smaller will weigh a bit less and be easier to install.  Larger won't have the tube stretched as much, so hypothetically could survive a puncture better.