If you are looking for link style golf, I would recommend Dunbar or Luffness. Luffness indeed had superb greens, and the course had a very similar feel to nearby Muirfield. Dunbar plays right along the ocean along a narrow strip of land. You see the sea almost every hole, and the winds can be amazing.
Otherwise, I would recommend Longniddry. One of the big surprises on our last Scotland trip. Some holes links like, some parkland, and in wondeful condition. No par 5's if I recall, a lot of long par 4's.
There are a lot of hidden gems that way. Ask the locals, we played a few. You will not be sorry. Have a great trip.