I walked the Heb Way in 2019 and it was one of the most SPECTACULAR experiences I have ever had. One of my walking friends and I said to each other afterwards, "Will we ever consider anything beautiful again? How could it possibly compare to the beauty of the Outer Hebrides?"
We used this guidebook:
https://www.amazon.ca/Hebridean-Way...-Hebrides/dp/1852847271/?tag=santiagodec0b-20
We did have to do a lot of advance booking & planning and we used a wide array of accommodations - from bunkhouses to bothies to fancy hotels. Once we got stranded (double booking at a bunkhouse) and a taxi driver not only came to get us, but found us a place to stay. I also got help once from a hotel that was booked up; the person at the front desk called around until they found us a spot and dropped us off there, free of charge! We also did a lot of self-catering - loading up at grocery stores and doing our own cooking, etc. We often found that other walkers and cyclists were happy to cook together and share meals.
My favourite hostels were the ones that are part of the Gatliff Trust:
https://gatliff.org.uk/ - in particular, Rhenigidale (although you have to schlep all of your food over the Postman's Pass and it's no joke; we met a cyclist there who didn't know it was without resources nearby and had nothing, so it was lucky for him that six of us showed up with stew provisions and whisky for all!). Honourable mention to Berneray, which is right on the beach.
I don't remember any problems on Sundays although it is true that most Lewis and Harris businesses are closed on Sunday. But a combo of advance planning & the kindness of locals will get you everything you need. I loved the Outer Hebrides deeply and I can't wait to go back. Happy to answer any other questions, although it looks like you've got a local upthread who will know more!