Colin,
Being an Aussie myself I'm no expert of the area, but I do know a little.
Apart from all the St. Andrew's courses - Old, New, Eden, Jubilee, which are all worth a hit, can I suggest:
Kingsbarns - A brilliant Kyle Phillips design. 6 holes right up against the North Sea. 12th hole very tempting.
The Golf House Club at Elie - An Old Tom Morris course that's quite quirky.
Crail Golfing Society (Both courses - Balcomie & Craighead links) Balcomie is an Old Tom Morris layout. Craighead is their new course designed by Gil Hanse.
Lundin Golf Club - Great land right next to the beach. (of sorts)
Levin Links Golf Club - Not far from Lundin GC.
The green fees at most of these courses aren't too bad. Kingsbarns will be the dearest at about 125 pound per round, but it is well worth it. TOC is about 90 pound per round.
I think you can still get a weekly ticket for all the St A courses (New, Eden, Jubilee, Strathtyrum, Balgove), except the Old, for about 190 pound.
I hope that helps.