Yrsa is a Rellekkan fashion designer and runs Yrsa's Accoutrements, and the makeover shop, Yrsa's Shoe Store. She plays a role in Sigmund the Merchant's task in The Fremennik Trials quest. She will change the colour and style of your shoes for free.
As with most Fremenniks who are traders, Yrsa will not change your shoes if you have not completed The Fremennik Trials quest.
Yrsa's Shoe Store
Yrsa offers a very wide variety of shoes (and shoe colours) that the player can choose from. It previously costed 500 coins to change your default shoes, but after the Court Cases update on 1 September 2010, the service became free.