New tires

In my opinion, the Continental Gatorskin Ultra is the best tire for flat-free cycling. It rides well and is practically puncture-proof. I've used them on my road bike for several years now and never had a flat. Sure, you'll pay about $40 per tire instead of perhaps $20 for tires that get flats, but isn't having no flats for thousands of miles worth $20? You can view several sizes on my site

a narrower tire would roll a little easier but you'd probably never go fast enough to feel a big difference, unless you wore low drag clothing and changed your seating position to lower your torso. The lighter weight would make acceleration a bit easier (weight is more important on a tire because you have to make it spin faster as well as move forward faster).

They also tend to not handle rocks and rain ruts as well. I frequently ride gravel trails and dirt roads with 1-3/8 wide tires but they are not as stable as wider ones. You gotta keep it out of the low spots where sand has built up and you gotta keep it out of the rain ruts.

Schwalbe makes a line of tires which is supposed to roll easier despite being balloon tires. I think they are called the Marathon and Big Apple. I have not tried them.