What Charles suggested is more polite. As he wrote, If you say タイヤを取り替えて欲しいんですが、、、(欲しいのですが・いただきたいのですが)、what you are really saying is, " I am wondering if you could change the tire for me ", "Would it be OK if I asked you to change the tire for me? ", etc.
While it is perfectly fine to say タイヤを交換してください, I think it is better to take the indirect aproach than directly stating your request, which could easily be mistaken for a demand. It has a lot to do with HOW you say it, too.