I'm sure someone has mentioned this before, but when things were tight I'd always go to Lidl, see what they had on sale and plan my meals around that. I could get an entire shopping bag full of produce for around £10-15 that lasted a week. They tend to not carry everything larger stores do, but what they do have always seems to be high quality compared to stores like Tesco. For example, they always had beautiful aubergines for 80p each, while the ones at Tesco were small and beat up for £1. And a huge bag of spinach was only £1 there, while it was £2 or more at Tesco. I never bought packaged, processed food, but you could get ridiculous deals, like a big package of biscuits for 20p and a jar of pasta sauce for 30p. I never bought meat there and only eat fish (and only occasionally), so I have no clue the best place to buy meat.
One thing that saved me a lot of money was looking at all of the store websites to find prices of things like soap, shampoo, deodorant, toothpaste, etc, and see who had the best deals. My husband's deodorant was usually £3 per bottle, but searching sales, I found it for less than half price at Asda and stocked up on 20 bottles. I did the same thing with shower gel - when it was half price, I bought 10 bottles. I had a lot of storage space in my bathroom for it, though. It was so much cheaper than grabbing a bottle when it was needed.
I can't comment on Costco in the UK, but now that I'm in Canada, I find them to have fantastic deals on food compared to other places. Equivalent produce is usually half the price there. If you have the space, I'd recommend buying frozen food in bulk, because it will always be cheaper.