Even the best workshops can do dud work sometimes (that's why i did a mechanics apprenticeship in my youth but obviously that's not for everyone) but here are two (after the fact) tips:
1. Don't self diagnose. If its overheating just tell them when and how it overheats and let them work out why. Ask them to give you a ring when they have a diagnosis and tell you what they propose to do and why and how much it is going to cost.
2. Go to the experts.
Radiator shop for overheating. With a car of your age the radiator will need cleaning out or re-coring and the plastic header tank is likely to develop splits. If there is another fault this won't be wasted money as it is the most likely cause and needed doing anyway. [btw the fact that the temp guage has not indicated overheating in the past means little because it is designed to sit in the normal setting until things get really hot]
Auto electrician for starter. Most mechanics have only a rudimentary knowledge of electrics and will fit new or recond exchange starters and alternators. Auto electrician will repair as necessary - poss bearings, bushes, clean up commutator etc - again a ten or more year old car will need this anyway. He can test your battery, alternator output and starter draw in 2 minutes.
If you can find evidence of poor or unnecessary work by the workshop take the bill to the boss and have a chat and ask for some money back.
Good luck