Yes, tyres make a big difference. I bought a used MTB and went out for a ride with a friend. I noticed that I was pedalling hard while he was free-wheeling, so I stopped to test that the wheels span freely, which they did, so I carried on confused.
A few days later, I decided to change the tyres, but I couldn't get them off. Finally after a lot of heave-ho, the first came over the rim and I could see the problem: There were two tyres on each wheel. There was a smaller knobbly tyre inside each of the bigger ones plus the tube. I chucked everything, and when I put the new tyres on, the bike was completely transformed.