I know quite a few folks are interested in their Celtic roots and so naturally gravitate in the Scottish direction. Irish seems to come next, with Cornish, Welsh and a little Brittany later, but you might also look into possible mainstream French connections. As you'll see from this article, the Scots and French were pretty well integrated a lot earlier than many people realise:

http://en.wikipedia.org/wiki/Garde_%C3%89cossaise

All the best
Graham.