-
Sounds like an epic trip but surprised you didn't like Skye-there's a lot of wee routes that are simply breathtaking but they can tend to lead out to peninsulas so you have to do out and back runs. The ride from Broadford to Elgol is simply amazing-last time I did it I saw eagles and everything...
Granted, if you're schlepping along that main road in the wind it's not fun, but there's also the old road that runs parallel to it along big sections, and the road from Sligachan up along the West to Colbost or Trumpay is fucking epic-very climby place to ride if you're fully loaded mind you and the midges are savage any time past April.
There's also a cracking ride from by Broadford to Kylerhea where there's a ferry taking you back over to the mainland, going over the old military road straight over the top of Glenelg and back round to the bridge at Kyleakin via Eilean Donan Castle, but again, very climby and would be tough fully loaded.
I cycled through the Outer Hebrides last summer - Barra, South Uist, North Uist, Harris, ferry to Skye, ferry to Mallaig, Fort William, Loch Ness, Inverness.
Favorite bits were the Barra, South Uist, Harris. Would definitely like to return to Harris for more exploring, and beaches. Cycling is fine there - mostly single track roads so it can get a bit stoppy/starty pulling over to let vehicles past. Excellent road surfaces.
Skye was a bit meh (just a long drag along the main road, and no alternative quieter routes).
Tried to follow the Sustrans route from Fort William to Inverness. Some parts of this are really terrible and hard going - pot-holled dirt track around Achnacarry, and deep chunky gravel on the canal path West of Fort Augustus. General Wade's Military Road from Fort Augustus to Inverness is a pleasure, as is the canal at the West end (Fort William to Gairlochy). Nice free flat camping spots are dotted along this canal.
From other Scottish trips - As @ùbér_grùbér says, I'd also recommend Applecross, and the desolate North Western bits.