My search for replacement shoelaces

You might try Walgreens, as well; they typically have an aisle with household thingies like shoelaces and shoe polish.

For athletic shoes, you can also try a sporting goods or running store.