It seems like you should be able to simply advertise the fact that yes, we cost exactly $20 more than the cheap guy. And here's all stuff you get for that (dignity, comfort, sodapop and your bags in the hold). And here's how small a fraction of your whole trip that $20 actually represents. And oh, here's how small a fraction of your whole trip the entire $179 you're paying for the flight is.
But there's just so much innumeracy and irrational behavior to overcome before you can get that message across. Try selling the above to the average flyer who will happily take the $159 seat on the airline that charges him $50 to check a bag over the $179 seat that doesn't have any added fees.
I hope somebody cracks it. It seems like you could do it with a whole bunch of published (and advertised) transparency in your pricing and value offered, combined with a campaign encouraging buyers to "sort by happiness" or whatever when browsing at kayak.com.