If the Muslims want the kosher products the deli offers, then yes, they must provide them.

Can the maid service refuse to clean the home of a Christian? No. If they provide a service they must provide it equally to anyone.

Does the welding shop create any statue for anyone? Then yes they need to provide that service equally. However, they can choose to not provide any religion-based statues, as that would be equal service (non-service) regardless of religion.