I continue to be amazed by the numerous posts asking this same question about various cities.
Best way to store luggage in just about any city: go to decent hotel, ask bell captain to store luggage, give him a couple of bucks, get claim check, pick up luggage, give person who brings you luggage a couple of bucks.
No need to be staying at hotel.