I can recommend http://www.arnoldclarkrental.com/ from a previous trip in Scotland. I don't know about any surcharges for young drivers, but their rates were very competitive back in 2011.