I did the same trip during a similar time frame and time of year and both the ferries to Orkney and Lewis were busy, so I suggest you book in advance.
Also check the ferry times to the various islands if you going to them as they required a little planning to fit into my timetable. When i was there you booked and paid at the local office in Kirkwall.

I was lucky and had good to excellent weather for the most part on Orkney.