Any !!!
From my limited experience of Scotland
I have been hiking there twice and in may.
In 2007 West Higland Way ( Glasgow- Fort William )i was recovering from back injury so i could have a bag carried for me every day ( lots of elder do this hike its easy and services of this kind are easy to get )
The landscape is great , even if sometime close to road, and you can socialize / drink / eat haggis.
I got sun burned , there was 0 midges , only some tics.
In 2009 i did the south part of cape wrath trail , starting at Fort William

( the photo is blurred from rain drops , and what you see is supposed to be a path…)
The weather was "Scottish" rain 24/24 7/7 ( even a little snow ), so no risk of midges.
But there was no fog so we enjoyed terrific landscapes, definitly one of the hike i liked the most.

My wife and i are planning to go back to do another part of this trail
Maybe in 2010 , Scotland in may and Patagonia in november, that would be nice :)
So as Mike said CWT in may is a great idea.
My only regret is i love fishing when i hike, ( we ate a dozen arctic chars, salmons , cabillaud this summer in Greenland )but seems its very complicated there , you need to buy a permit to fish according to the river/lac you want to fish in , no global license, that doesnt go well with hiking.