I agree that both Orkney and Skye are tough in your time frame. You will just have to come back! Wait, I'm not in Scotland right now, unfortunately, so it's "go back"! :)
Get with ever tickets are cheaper. They are very close together. I would definitely rent a car as you want to visit Skye. While I suspect you could rent a van, you might want to go with two smaller cars. The road are wee and unless you are comfortable driving a van, you might find challenges. Try the transportation forum, though to see if there are any suggestions.
I agree that the boat ride to Loch Coruisk is great, but even if you just go to Elgol--it's a beautiful drive--and check out the view of the Cuilins from the pier it will be good! There are fewer yet people on Harris and Lewis, but I am a bit concerned about time as the ferry ride is longish and again you need at least two nights, preferably three. Instead you might explore the more remote parts of Skye. Skye has many arms and most people go to Portree, check out Dunvegan, check out the Cuilins, maybe go around Trotternish, but the other "arms" are much less explored.
So, go beyond Dunvegan and up to Waternish. If you want to walk on one of the Coral Beaches there is one just north of Dunvegan. Also, there are craft shops....
Also, think about going to Duirinish. The lighthouse at Neist Point is amazing. (On the way west you drive past Skye Silver which is worth a stop if you like jewelry. I still mourn the necklace that bought there which was lost on another trip. Undiscovered Scotland can provide you with more places to look for.
The Trotternish is worth exploring too. Look for a standing stone on the west coast near Eyre. Also, a little further on is St. Columba's Isle and Burial Ground which it well worth stopping for.
I've driven out to Loch Brittle on the west coast for a photo shoot and it was beautiful. It might be interesting to explore the west coast of Skye. At the very least it looks like there are some Brochs to explore.
Lastly, if you are looking for a place with even fewer people, think about exploring Ardnamurchan. Do fill up the gas tank before driving out there!