You're spoilt for choice in Edinburgh! I was working there a couple of years ago and used to go in The Royal Oak - brilliant little pub. There's music there every night I think, but Tuesday is a session night..Best thing is to give them a call. The link to their website is below
http://www.royal-oak-folk.com/