Advisor asks me to use plots that favor our approach, saying "the numbers in our paper don't matter; what matters is the message" My advisor has been asking me to generate plots I am uncomfortable with, since they overestimate the success of our approach, or make the data seem less noisy than it is.  He says this is okay because the numbers in the paper don't matter as much as the high level message.  What should I do?

We haven't fabricated data per se but some of the analyses are sketchy. For example in one plot we are comparing our approach to a baseline, but due to lack of data, any point that our approach fails on will also register as a failure when we apply the baseline method to it, meaning our approach will always look better. 

Due to lack of data, there's no obvious "alternative plot"; the alternative would be not generating any plot, or generating a plot that underestimates the success of our approach (which he says is just as bad as overestimating its success).  In some cases, our plot and another plot are equally defensible, but our plot looks a lot better so we kept it.
Standard definitions of scientific misconduct consider omission of conflicting data an instance of data falsification, see, for example, the guidelines as applied by the BMJ, or Gupta 2013 on fraud and misconduct:


  Falsifying data means altering the existing records. It is the deliberate distortion or omission of undesired data or results. 


If your advisor asks you to deliberately produce a figure that downplays undesired results, he or she is asking you to falsify your data.

So, what should you do? 

Speak again to your advisor. Tell him or her that you don't feel comfortable with the suggested plot, and explain that you feel obliged to report the data faithfully, including weaknesses of the analysis and conflicting observations.

If your advisor insists on using the falsifying plot, you should consider choosing a different advisor, because the present one may not teach you proper scientific conduct.