Hi VJ, I would see if you can take it back and sort it out, the only problem I can see is how do you prove that it had different tyres on it? and why would they change them? are the tyres you now have a cheaper version of the ones you originally had? If you happen to have the original receipt that has the tyre type on it then you have something to work with but otherwise your up the creek!! Do you happen to know a solicitor/lawyer that might be able to advise you on what you can do, the laws in your country might be different to those here and so there might be nothing that can be done, try talking to the owner/manager of the workshop to find out why they nicked your tyres and he might have a good reason for the change, you never know till you ask. Otherwise start a facebook page and shame them on it, might get you into trouble with the local authorities tho as accusing someone of theft is not a thing to be done lightly. Best I can suggest but others might have a better solution on here?
PS NEVER NEVER go there again regardless of what the outcome is, I don't care what they say about this and their reasons they are crooks and should be put out of business even if it means you have to go else where for your servicing, and tell everyone who will listen how you have been treated.