Harris is very good for walking, but all the hills are quite steep and rocky, and though they aren't all that high, you are always starting from sea level. However, there are plenty of lower level walks if the hills seem a bit daunting, often old paths linking settlements (some now deserted) from before the roads were built. The beaches on the west coast are beautiful.
If you decide to go out to the islands it is worth considering visiting more than one. The Uists are very different from Harris and Lewis, and Barra is different again, and there are frequent ferries between them. There is a new long distance walking route which links them all, which might give a few ideas for walks.
In the summer accommodation tends to get booked up, if you are relying on hotels and b&bs you will need to book ahead.