The tires definitely seem like a good candidate. Probably your whole wheels are heavier as well which can really make a ride seem sluggish.

When you say "pedal straps seem like an obvious choice" does that mean you don't have any foot retention?