Here tours start from June 1 - http://www.landmannalaugartours.com/
You keep on mentioning this company #3. Do you have any connection with them? Do you know precisely how they achieve this date?
As I mentioned in another thread, you can go to L in a road vehicle when the road is open, and you can go there in a snow vehicle if the snow cover is sufficiently complete. Being a tour operator does not exempt you from these basic rules of travel in Iceland. So there has to be an interim period between the winter and summer tours when you can't go there in any surface travel vehicle, only a helicopter.
So my guess is that this 1 June date means that they will go there as soon as the road opens, which on rare occasion is as early as 1 June, but usually is rather later in the month. And just because the transport goes there, doesn't mean the trek is suitable for you at that date, there are plenty of people who go there for other reasons. For example Thmk is usually accessible by early to mid May, but that doesn't mean the Thmk-Skogar trek is doable by ordinary trekkers that early.
If you trek to/from L in early June, there will be substantial snowbands and they won't be well trodden yet, so if you aren't a brilliant trekker happy about walking a lot over snow, it isn't for you. Most deaths on the L-T hike occur in the shoulder season before there is substantial passing traffic. The most common cause of death is hypothermia. This is because there isn't the passing trekker traffic to notice you and rescue you if you fall and immobilise yourself. The cellphone coverage has got better in recent times, so you can call out helicopter rescue if you have the phone coverage and can get to the phone, but it definitely isn't complete coverage and there will be extended dead spots on such a hike because of the folded terrain.
Access to Kerlingarfjoll will be trickier because it is much less visited.
compass
Not much use in Iceland because of large and localised magnetic deviation and the common occurrence of magnetised minerals in the ground. If you need a navigation aid, a GPS would be better.
Any alternative trek to suggest in this period of the year?
There are plenty of forum threads on this, search the forum for what you find, then come back with Qs. But realise that you are coming too early for a very good choice. You might also wish to consider buying yourself a copy of the Cicerone guide to trekking in Iceland, it has about 10 longer treks as well as a longer list of day-walks.
