Shoes are stiff when they are new.
FYI: かたい can be spelled as 1) 固い, 2) 硬い, or 3) 堅い. Many of Japanese native speakers don’t fully understand the difference and often misuse among them.
固い – the antonym is 緩い（ゆるい）= loose
硬い – the antonym is 軟らかい（やわらかい）= soft
堅い – the antonym is もろい = fragile/breakable
If the new shoes have a solid sole made of leather, and it can be softened after using for a while, the correct Kanji is 2) 硬い.
If the new shoes are fully made of leather, can be expandable and better fit the shape of your foot, it should be 1) 固い.
I believe 2) 硬い is the correct Kanji. My argument is based on an article written by the professional proofreading team at Mainichi Newspaper.