Not sure if they are allowed to treat credit card customer's differently, there must be some policy that says you can't charge extra if your customer is paying by credit cards.
Many brick-and-mortar shops don't accept CC at all (in UK) due to high fees (they do accept debit cards tho), or have a minimum purchase amounts set for cc payments. So I don't think it would be any sort of illegal 'discrimination'.
Either way, you can just do it as "discount for paying BTC", not as an extra charge for using CC. Like the Newegg and others did.
As for Overstock, $3m sales in bitcoin is actually pretty decent result if you ask me. Their predictions were just too optimistic, that's another story.
I think bitcoin discounts are just a matter of time. So far all the (large) businesses could get all the love from the community just by mere fact they started to accept bitcoin, they'll soon realise that in a long run - that's simply not enough.