Лакост есть в Foot Locker на calle carmen, это между gran via и puerto del sol. центр города, куча туристов, если спросишь, тебе покажут. там же где-то в окресностях я видел какой-то жутковатый скейт-шоп с очень скудным выбором creative recreation, но все-таки что-то там было.

а так вообще если в центре смотреть, то с кедами у них проблемы, это тебе не Амстердам))) может быть где-то есть магазины специализированные, но видимо они находятся где-то в жопе и известны только местным.