Hiya!
Mrs G and I went in September in 2004 and I was in shorts and sandals for the duration! Not cos I'm mental, but because the weather was excellent. ;) And I got sunburned. Totally unexpected...
We didn't eat out either, so can't recommend anywhere - we went self-catering so just ate in and made picnics.
Oh god I'm so jealous. Ever since we got back we've yearned to get back up there! I don't think I can add anything to other recommendations, but the well-known sites are all superb, and will definately keep you busy!
We went for a little well-hunt one day but gave up after 2 or 3 finds... Not cos we couldn't be arsed, but there was just so much else to see! Thought we'd save it for another visit, maybe... :)
Tomb of the Eagles is on South Ronaldsay, which, as has been discussed, is joined by the Churchill Barriers to Mainland Orkney. You gotta get yerself down there!
I also recommend a day trip to North Ronaldsay. You want remote? Well, there it is! There's several tumuli and a standing stone if you need an excuse... The beach-dwelling, seaweed-eating sheep are excuse enough for me! :)
We stayed in a couple of places - one overlooking the Loch of Stenness (with the Ring o' Brogar and Maes Howe visible from the roof garden) and some fantastic holiday chalets in Finstown, in sight of the Cuween chambered tomb. I can give you more details if you need them!
G x