Beauty-wise: I tend to buy the majority of my Chanel at Murale; I'm aware this isn't in the States but you get Optimum Points. If I absolutely have to (i.e - the product is sold out at Murale) I'll go to the Bay - because I'll get HBC points. The Bay does send out 'Extra 25 000 Points' coupons if you spend X amount of money monthly so it works out well.
I don't think a department store CC is REALLY nessecary; I know The Bay's annual charges & fees is pretty steep in comparison to other bank CCs so I skip and just have my VISA. I find my Rewards card is enough, but it also depends how much you spend at department stores. I don't go to department stores much apart for the odd topshop item, my hair, or my MAC fix.