I have eaten and stayed at www.threechimneys.co.uk which is simply fantastic. Its a restaurant with rooms and I would recommend it if you want to have a splurge.
We like to take the ferry over from Mallaig - best fish and chips in the world and some stunning beaches, and then drive back round via the Kyle of Lochalsh.
If you want some fish then Andy Race who is based in Mallaig is the place to get some from. almost 10 years ago
I have been in 2008 in Dun Flodigarry Hostel close to Staffin in the very middle of Quirang on Skye. Fantastic views on hills over Flodigarry, great views on the sea just in front of the hostel. Great atmosphere.
Check it out here:
http://www.hostelflodigarry.co.uk/ about 9 years ago