Suggesting an alternative to referee/reviewer recommendation
In my reply to the referee, I will explain why I did C and why I think that approach C is better than A and B


This is essentially all you need to do. You don't need to follow reviewers' recommendations slavishly, but if you do decide to deviate from their recommendations, you should explain why. Which you plan on doing. In the end, it comes down to the editor's decision, so you should always strive to make his life easy, by explaining what you do and why.


  "I am open to the possibility that the referee might still prefer approaches A and B. If that is the case, I will switch to these approaches in the eventuality of a further revision, should the referee request it."


This adds a nice touch, without appearing subservient. I'll keep this in mind for the next time I decide not to follow a reviewer's recommendations ;-)

Bottom line: I'd say you are doing exactly the right thing.



EDIT: Bonus points if you can and do write something along these lines in your response to the reviewer:


  "In addition to C, which is described in the manuscript, I also did A and B, as suggested by the reviewer. The results, as measured by Y, are similar/inferior/whatever to the results of doing C, in the following way:..."


And I do see the point raised by @xLeitix in his comment. The "open to the possibility" should not come across as "I'll use an inferior approach just to get published", but rather as "if opinions about A/B vs. C can differ reasonably, I am open to..."